HDU 4374--F(x)

F(x)

Time Limit:1 Seconds Memory Limit:32 MB

Description

For a decimal number x with n digits (A_nA_n-1A_n-2 ... A₂A₁), we define its weight as F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 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 < 10⁹)

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

3 0 100 1 10 5 100

Sample Output

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

Source:

2013 ACM/ICPC Asia Regional Chengdu Online

题目意思很简单，按要求计算0-B之间的F（x）值，算小于等于F（A）的个数。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <string>
 6 #include <cmath>
 7 using namespace std;
 8 
 9 int dp[11][10001];  //dp[i][j] ..表示i位数 <= j的个数
10 int bit[11];   //记录每一位
11 
12 int F(int x)
13 {
14     int sum = 0;
15     int mul = 0;
16     while(x)
17     {
18         int y = (x % 10) * (1 << mul);
19         sum += y;
20         mul++;
21         x /= 10;
22     }
23     return sum;
24 }
25 
26 int A,B;
27 int t;
28 
29 int dfs(int pos,int num,int full)
30 {
31     if(pos == -1)return num >= 0;                         //求到最低位做出判断
32     if(num < 0)return 0;
33     if(!full && dp[pos][num] != -1)return dp[pos][num];  //返回记忆化的值
34     int end = full?bit[pos]:9;                             //取该位的最大值
35     int ans = 0;
36     for(int i = 0;i <= end;i++)
37     {
38         ans += dfs(pos - 1,num - i * (1 << (pos)) ,full && i == end);
39     }
40     if(!full)dp[pos][num] = ans;                         //记忆化记录
41     return ans;
42 }
43 
44 int Cal()
45 {
46     int y = B;
47     int cnt = 0;
48     while(y)
49     {
50         bit[cnt++] = y % 10;
51         y /= 10;
52     }
53     return dfs(cnt - 1,F(A),1);
54 }
55 
56 int main()
57 {
58     scanf("%d",&t);
59     int cas = 1;
60     memset(dp,0xff,sizeof(dp));
61     while(t--)
62     {    
63         scanf("%d%d",&A,&B);
64         printf("Case #%d: %d
",cas++,Cal());
65     }
66     return 0;
67 }

View Code