2015
04-14

# K-th Nya Number

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.

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 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).

1
38 400 1 1
10
1
2
3
4
5
6
7
8
9
10

Case #1:
47
74
147
174
247
274
347
374
Nya!
Nya!

by—cxlove

HDU 3943 K-th Nya Number

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
LL dp[25][25][25];
//dp[i][j][k]表示i位的数，有j个4，k个7的数量
LL l,r;
int x,y;
void Init(){
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1;i<21;i++){
for(int j=0;j<i;j++)
for(int k=0;k<i;k++)
if(j+k<i){
dp[i][j][k+1]+=dp[i-1][j][k];
dp[i][j+1][k]+=dp[i-1][j][k];
dp[i][j][k]+=dp[i-1][j][k]*8;
//在高位加上除了4、7以外的8个数字
}
}
}
LL get_count(LL n){
int bit[25],len=0;
while(n){
bit[++len]=n%10;
n/=10;
}
LL  ans=0;
int cx=x,cy=y;
for(int i=len;i;i--){
//从高位开始枚举
for(int j=0;j<bit[i];j++)
if(j==4){
if(cx)
ans+=dp[i-1][cx-1][cy];
}
else if(j==7){
if(cy)
ans+=dp[i-1][cx][cy-1];
}
else
ans+=dp[i-1][cx][cy];
if(bit[i]==4)
cx--;
if(bit[i]==7)
cy--;
//如果高位出现的4、7数量已经超过要求，则退出
if(cx<0||cy<0)
break;
}
return ans;
}
LL slove(LL k){
int len=1;
while(1){
//找到目标数的长度
if(dp[len-1][x][y]<k&&dp[len][x][y]>=k)
break;
len++;
}
LL ret=0;
int cx=x,cy=y;
for(int i=len;i;i--){
//从高位开始从小枚举
for(int j=0;j<10;j++){
int tx=cx,ty=cy;
if(j==4){
tx--;
if(tx<0)
continue;
}
if(j==7){
ty--;
if(ty<0)
continue;
}
if(dp[i-1][tx][ty]>=k){
ret=ret*10+j;
cx=tx;
cy=ty;
break;
}
k-=dp[i-1][tx][ty];
}
}
return ret;
}
int main(){
int t,cas=0;
scanf("%d",&t);
Init();
while(t--){
scanf("%I64d%I64d%d%d",&l,&r,&x,&y);
LL a=get_count(r+1);
LL b=get_count(l+1);  //注意是左开区间，悲剧了好久
int q;
scanf("%d",&q);
printf("Case #%d:\n",++cas);
while(q--){
LL k;
scanf("%I64d",&k);
if(k>a-b)
puts("Nya!");
else
printf("%I64d\n",slove(k+b));
}
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。