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

 

Source

2010
ACM-ICPC Multi-University Training Contest（12）——Host by WHU

 

Recommend

zhouzeyong   |   We have carefully selected several similar problems for you:  

pid=3554" style="color:rgb(26,92,200); text-decoration:none">3554 3556 3557 3558 3559 

 

这样的比递推的那种写法慢了些啊

ac代码

#include<stdio.h>

#include<string.h>

int bit[20];

__int64 dp[20][10][2];

__int64 dfs(int pos,int pre,int isture,int limit)

{

	if(pos<0)

	{

		return isture;

	}

	if(!limit&&dp[pos][pre][isture]!=-1)

	{

		return dp[pos][pre][isture];

	}

	int last=limit?

bit[pos]:9;

	__int64 ans=0;

	for(int i=0;i<=last;i++)

	{

		ans+=dfs(pos-1,i,isture||(pre==4&&i==9),limit&&(i==last));

	}

	if(!limit)

	{

		dp[pos][pre][isture]=ans;

	}

	return ans;

}

__int64 solve(__int64 n)

{

	int len=0;

	while(n)

	{

		bit[len++]=n%10;

		n/=10;

	}

	return dfs(len-1,0,0,1);

}

int main()

{

	int n;

	memset(dp,-1,sizeof(dp));

	int t;

	scanf("%d",&t);

	while(t--)

	{

		__int64 n;

		scanf("%I64d",&n);

		printf("%I64d\n",solve(n));

	}

}

人家的代码http://blog.csdn.net/scf0920/article/details/42870573

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

using namespace std;

#define LL __int64

#define pi acos(-1.0)

const int mod=100000000;

const int INF=0x3f3f3f3f;

const double eqs=1e-8;

LL dp[21][11], c[21];

LL dfs(int cnt, int pre, int maxd, int zero)

{

    if(cnt==-1) return 1;

    if(maxd&&zero&&dp[cnt][pre]!=-1) return dp[cnt][pre];

    int i, r;

    LL ans=0;

    r=maxd==0?

c[cnt]:9;

    for(i=0;i<=r;i++){

        if(!zero||!(pre==4&&i==9)){

            ans+=dfs(cnt-1,i,maxd||i<r,zero||i);

        }

    }

    if(maxd&&zero) dp[cnt][pre]=ans;

    return ans;

}

LL Cal(LL x)

{

    int i, cnt=0;

    while(x){

        c[cnt++]=x%10;

        x/=10;

    }

    return dfs(cnt-1,-1,0,0);

}

int main()

{

    int t;

    LL n;

    scanf("%d",&t);

    memset(dp,-1,sizeof(dp));

    while(t--){

        scanf("%I64d",&n);

        printf("%I64d\n",n+1-Cal(n));

    }

    return 0;

}