HDU 4734 F(x)

F(x)

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 768 Accepted Submission(s): 296

Problem 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

Sample Output

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

Source

2013 ACM/ICPC Asia Regional Chengdu Online

Recommend

liuyiding

很不错的dp题目，折磨好几天后终于ac了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 5000
#define M 10
using namespace std;
int dp[M][M][N];
int a[M],b[M];
int main()
{
    a[1]=1;
    for(int i=2;i<=9;i++)
    {
        a[i] = a[i-1]*2;
    }
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=9;i++)
    {
        for(int j=i;j<=4608;j++)
        {
            dp[1][i][j]=1;
        }
    }
    for(int i=2;i<=9;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int x=a[i]*j;x<=4608;x++)
            {
                for(int y=0;y<=9;y++)
                {
                    dp[i][j][x]+=(dp[i-1][y][x-a[i]*j]);
                }
            }
        }
    }
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        int s=0,base=1;
        while(n!=0)
        {
            s+=((n%10)*base);
            base=base*2;
            n=n/10;
        }
        int Top=0,com=0;
        base=1;
        while(m!=0)
        {
            b[Top++] = m%10;
            com+=(b[Top-1]*base);
            base=base*2;
            m = m/10;
        }
        int res =0;
        if(com<=s)
        {
            res++;
        }
        for(int i=Top-1;i>=0;i--)
        {
            int x = b[i];
            for(int j=0;j<=x-1;j++)
            {
                res+=(dp[i+1][j][s]);
            }
            s-=(x*a[i+1]);
            if(s<0)
            {
                break;
            }
        }
        printf("Case #%d: %d
",cas++,res);
    }
    return 0;
}