HDU 3555 Bomb

Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 5247 Accepted Submission(s): 1815

Problem Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

3

1

50

500

Sample Output

0

1

15
Hint

From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499", so the answer is 15.

Author

fatboy_cw@WHU

题意：求1--N，包含49的个数，注意：数字4949只算一次。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef __int64 LL;
 5 LL dp[21][11];
 6 void prepare()
 7 {
 8     LL i,j,cur,s;
 9     memset(dp,0,sizeof(dp));
10     for(i=4;i<=9;i++)   dp[2][i]=1;
11     for(i=3;i<=20;i++)
12     {
13         for(j=0;j<=9;j++)
14         {
15             if(j==0)
16                 dp[i][j]+=dp[i-1][9];
17             else
18             {
19                 dp[i][j]=dp[i][j]+dp[i][j-1];
20                 if(j==4)
21                 {
22                     dp[i][j]=dp[i][j]+dp[i-1][8];
23                     for(cur=1,s=i-2;s>0;s--)
24                         cur=cur*10;
25                     dp[i][j]=dp[i][j]+cur;
26                 }
27                 else dp[i][j]=dp[i][j]+dp[i-1][9];
28             }
29         }
30     }
31 }
32 int main()
33 {
34     LL T;
35     LL n,i,j,k,tom,cur,glag;
36     char a[30];
37     prepare();
38     scanf("%I64d",&T);
39     while(T--)
40     {
41         scanf("%s",a+1);
42         k=strlen(a+1);
43         n=k;
44         for(i=1,tom=0,glag=0;i<=k;i++)
45         {
46             cur=(a[i]-'0')-1;
47             if(cur==-1);
48             else tom=tom+dp[n][cur];
49             if(glag==2) glag--;
50             if(glag==1) break;
51             if(a[i]=='4' && i+1<=k && a[i+1]=='9')
52             {
53                 glag=2;
54                 for(j=i+2,cur=0;j<=k;j++)
55                 {
56                     cur=cur*10+(a[j]-'0');
57                 }
58                 tom=tom+cur+1;
59             }
60             n--;
61         }
62         printf("%I64d
",tom);
63     }
64     return 0;
65 }