程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3943 K-th Nya Number（數位dp+二分）

HDU 3943 K-th Nya Number（數位dp+二分）

編輯：C++入門知識

HDU 3943 K-th Nya Number（數位dp+二分）

Problem Description 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.

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

Sample Input

Sample Output

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

Author hzhua

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef __int64 ll;

#define fre(i,a,b)  for(i = a; i = a;i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define ssf(n)      scanf("%s", n)
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;

#define INF 0x3f3f3f3f
#define N 25

ll dp[N][N][N];
int bit[N];
ll le,ri;
int x,y,k;

ll dfs(int pos,int prex,int prey,int bound)
{
   if(pos==0) return prex==0&&prey==0;

   if(prex<0||prey<0) return 0;

   if(!bound&&dp[pos][prex][prey]!=-1) return dp[pos][prex][prey];

   int up=bound ? bit[pos]:9;

   ll temp=0;
   int i;
   fre(i,0,up+1)
   {
   	  temp+=dfs(pos-1,prex-(i==4),prey-(i==7),bound&&i==up);
   }
   if(!bound) dp[pos][prex][prey]=temp;
   return temp;
}

ll fdd(ll n)
{
   int len=0;
   while(n)
   {
   	bit[++len]=n%10;
   	 n/=10;
   }
   return dfs(len,x,y,1);
}

void solve()
{
  ll prex=fdd(le);
  ll prey=fdd(ri);
  ll lle=le,rri=ri;
  ll mid,ans;
  k+=prex;

  while(lle<=rri)
  {
  	mid=(lle+rri)>>1;
  	if(fdd(mid)>=k)
	{
		ans=mid;
		rri=mid-1;
	}
    else
		lle=mid+1;
  }
   pf("%I64d\n",ans);
}

int main()
{
	int i,j,t,ca=0;
	sf(t);
	mem(dp,-1);

	while(t--)
	{
		pf("Case #%d:\n",++ca);
		scanf("%I64d%I64d",&le,&ri);
		sff(x,y);
		ll numle=fdd(le);
		ll numri=fdd(ri);

		//pf("%I64d %I64d\n",numle,numri);
		int m;
		sf(m);
		while(m--)
		{
			sf(k);
			if(numle+k>numri)
				puts("Nya!");
			else
				solve();
		}
	}
   return 0;
}