HDU 4734 F(x)

F(x)

Time Limit: 500ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 4734
64-bit integer IO format: %I64d Java class name: Main

For a decimal number x with n digits (AnAn-1An-2 ... A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 109)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

Sample Output

Case #1: 1
Case #2: 2
Case #3: 13

Source

2013 ACM/ICPC Asia Regional Chengdu Online

解题：数位dp

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int dp[10][200010],pos[10];
 4 int F(int x) {
 5     int b = 1,ret = 0;
 6     while(x) {
 7         ret += x%10*b;
 8         x /= 10;
 9         b <<= 1;
10     }
11     return ret;
12 }
13 int dfs(int len,int now,bool flag) {
14     if(len < 0) return now >= 0;
15     if(now < 0) return 0;
16     if(!flag && dp[len][now] != -1) return dp[len][now];
17     int d = flag?pos[len]:9,ret = 0;
18     for(int i = 0; i <= d; ++i)
19         ret += dfs(len-1,now-i*(1<<len),flag&&i==d);
20     if(!flag) dp[len][now] = ret;
21     return ret;
22 }
23 int calc(int a,int b) {
24     int cnt = 0;
25     while(b) {
26         pos[cnt++] = b%10;
27         b /= 10;
28     }
29     return dfs(cnt-1,F(a),true);
30 }
31 int main() {
32     int kase,a,b;
33     scanf("%d",&kase);
34     memset(dp,-1,sizeof dp);
35     for(int cs = 1; cs <= kase; ++cs) {
36         scanf("%d%d",&a,&b);
37         printf("Case #%d: %d
",cs,calc(a,b));
38     }
39     return 0;
40 }

View Code