HDOJ 3652 B-number

B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1561    Accepted Submission(s): 854

Problem Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

 

Input

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

 

Output

Print each answer in a single line.

 

Sample Input

13
100
200
1000

 

Sample Output

1
1
2
2

 

Author

wqb0039

 

Source

2010 Asia Regional Chengdu Site —— Online Contest

 

Recommend

lcy

 

加一个参数记录%13的余数。。。。newres=(res×10+i)%13

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dp[20][20][3],n,bit[20],len; /*     dp『位』『余数』『状态』     0--->没有13     1--->没有13但是前面一位是1     2--->有13 */ int dfs(int pos,int res,int s,bool limit) {     if(pos==-1)         return (s==2)&&(res==0);     if(!limit&&~dp[pos][res][s])         return dp[pos][res][s];     int end=limit?bit[pos]:9;     int ans=0;     for(int i=0;i<=end;i++)     {         int newres=(res*10+i)%13;         int news=s;         if(s==0&&i==1)             news=1;         else if(s==1&&i==3)             news=2;         else if(s==1&&i==1)             news=1;         else if(s==1&&i!=1)             news=0;         ans+=dfs(pos-1,newres,news,limit&&i==end);     }     if(!limit)         dp[pos][res][s]=ans;     return ans; } int main() {     memset(dp,-1,sizeof(dp));     while(scanf("%d",&n)!=EOF)     {         len=0;         while(n)         {             bit[len++]=n%10;             n/=10;         }         printf("%d\n",dfs(len-1,0,0,true));     }     return 0; }

* This source code was highlighted by YcdoiT. ( style: Pastie )