K-th Nya Number
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 394364-bit integer IO format: %I64d Java class name: Main
Arcueid likes nya number very much.
A nya number is the number which has exactly X fours and Y sevens(If X=2 and Y=3 , 172441277 and 47770142 are nya numbers.But 14777 is not a nya number ,because it has only 1 four).
Now, Arcueid wants to know the K-th nya number which is greater than P and not greater than Q.
A nya number is the number which has exactly X fours and Y sevens(If X=2 and Y=3 , 172441277 and 47770142 are nya numbers.But 14777 is not a nya number ,because it has only 1 four).
Now, Arcueid wants to know the K-th nya number which is greater than P and not greater than Q.
Input
The first line contains a positive integer T (T<=100), indicates there are T test cases.
The second line contains 4 non-negative integers: P,Q,X and Y separated by spaces.
( 0<=X+Y<=20 , 0< P<=Q <2^63)
The third line contains an integer N(1<=N<=100).
Then here comes N queries.
Each of them contains an integer K_i (0<K_i <2^63).
The second line contains 4 non-negative integers: P,Q,X and Y separated by spaces.
( 0<=X+Y<=20 , 0< P<=Q <2^63)
The third line contains an integer N(1<=N<=100).
Then here comes N queries.
Each of them contains an integer K_i (0<K_i <2^63).
Output
For each test case, display its case number and then print N lines.
For each query, output a line contains an integer number, representing the K_i-th nya number in (P,Q].
If there is no such number,please output "Nya!"(without the quotes).
For each query, output a line contains an integer number, representing the K_i-th nya number in (P,Q].
If there is no such number,please output "Nya!"(without the quotes).
Sample Input
1 38 400 1 1 10 1 2 3 4 5 6 7 8 9 10
Sample Output
Case #1: 47 74 147 174 247 274 347 374 Nya! Nya!
Source
解题：数位dp+二分
1 #include <bits/stdc++.h> 2 using namespace std; 3 using LL = long long; 4 const int maxn = 22; 5 LL dp[maxn][maxn][maxn]; 6 int bt[maxn],x,y; 7 LL dfs(int len,int a,int b,bool flag){ 8 if(len == -1) return a == x && y == b; 9 if(!flag && dp[len][a][b] != -1) return dp[len][a][b]; 10 int u = flag?bt[len]:9; 11 LL ans = 0; 12 for(int i = 0; i <= u; ++i){ 13 if(i == 4) ans += dfs(len-1,a + 1,b,flag&&i == u); 14 else if(i == 7) ans += dfs(len-1,a,b + 1,flag&&i==u); 15 else ans += dfs(len-1,a,b,flag&&i==u); 16 } 17 if(!flag) dp[len][a][b] = ans; 18 return ans; 19 } 20 LL solve(LL x){ 21 int cnt = 0; 22 while(x){ 23 bt[cnt++] = x%10; 24 x /= 10; 25 } 26 return dfs(cnt - 1,0,0,true); 27 } 28 int main(){ 29 int kase,m,cs = 1; 30 scanf("%d",&kase); 31 while(kase--){ 32 LL P,Q,K; 33 scanf("%I64d%I64d%d%d",&P,&Q,&x,&y); 34 memset(dp,-1,sizeof dp); 35 scanf("%d",&m); 36 printf("Case #%d: ",cs++); 37 LL tmp = solve(P); 38 while(m--){ 39 scanf("%I64d",&K); 40 K += tmp; 41 LL low = P + 1,high = Q,ans = -1; 42 while(low <= high){ 43 LL mid = (low + high)>>1; 44 if(solve(mid) >= K){ 45 ans = mid; 46 high = mid - 1; 47 }else low = mid + 1; 48 } 49 if(ans == -1) puts("Nya!"); 50 else printf("%I64d ",ans); 51 } 52 } 53 return 0; 54 }