描述

传送门：hdu-4734

For a decimal number $x$ with $n$ digits $ (A_n A_{n-1}A_{n-2} … A_2 A_1) $, we define its weight as $F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + … + A_2 * 2 + A_1 * 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^9)$

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.

Examples

intput
1
2
3
4
3
0 100
1 10
5 100
output
1
2
3
Case #1: 1
Case #2: 2
Case #3: 13

大致题意

我们定义十进制数x的权值为$F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + … + A_2 * 2 + A_1 * 1$，a(i)表示十进制数x中第i位的数字。题目给出a，b，求出0~b有多少个不大于f(a)的数。

思路

由于每一位数乘的就是$2^{pos}$很容易想到用dp[pos][sum]来表示: 枚举pos的时候，当前未计算完的F(x)为sum时有多少个符合条件的数，边界就是check一下sum是否大于F(a)。

但是这样会TLE，因为这样做dp数组的值就和输入值有关系（check的是sum>F(a)就和输入的a有关），所以组测试数据都要重新给dp数组重新赋初值，就会TLE，所以需要换个思路。

用dp[pos][sum]表示，枚举到pos位时还差F(a) sum时有多少个符合条件的数，这样就dp就和输入无关了，就可以只初始化一次。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod=1e9+7;
typedef long long ll;

int a[10],fa,dp[10][5000];  //fa=f(a)  dp[i][j]: 枚举到第i位时当前比f(a)小j

int f(int x){
    int sum=0,p=0;
    while(x){
        sum+= (x%10)*(1<<p);
        x/=10;p++;
    }
    return sum;
}

int dfs(int pos,int sum,int limit){ //sum: f(a)-
    if(sum<0) return 0;         //sum小于0表示 比f(a)大。
    if(pos==-1) return 1;       //sum大于0表示 比f(a)小。
    if(!limit&&~dp[pos][sum]) return dp[pos][sum];
    int up=limit? a[pos]:9,tem=0;
    rep(i,0,up)
        tem+=dfs(pos-1,sum-i*(1<<pos),limit&&i==a[pos]);   //1<<pos: 2^pos
    if(!limit) dp[pos][sum]=tem;
    return tem;
}

int Count(int x){
    int pos=-1;
    while(x){
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,fa,1);
}

int main(){

    int T,A,B;
    scanf("%d",&T);
    CRL(dp,-1);
    rep(Case,1,T){
        scanf("%d%d",&A,&B);
        fa=f(A);
        printf("Case #%d: %d\n",Case,Count(B));
    }

    return 0;
}