数位DP-URAL-1057-Amount of Degrees

Amount of Degrees
Time limit: 1.0 second
Memory limit: 64 MB
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.
Input
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
Output
Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.
Sample
input output
15 20
2
2
3
Problem Source: Rybinsk State Avia Academy

17=2^4+2^0
18=2^4+2^1
20=2^4+2^2

``//// main.cpp// ural1057//// Created by 袁子涵 on 15/11/3.// Copyright © 2015年 袁子涵. All rights reserved.//// 15ms 388KB#include <iostream>#include <string.h>#include <stdio.h>#include <stdlib.h>#include <math.h>#include <algorithm>using namespace std;int X,Y;int dp[32][32];int K,B;void handle(){ for (int i=2; i<32; i++) {dp[i][0]=1;for (int j=1; j<=i; j++) {dp[i][j]=dp[i-1][j-1]+dp[i-1][j];} }}int DP(int N){ int num[32],k=0,flag=-1,sum=0,need=K; memset(num, 0, sizeof(num)); while (N) {num[++k]=N%B;N/=B; } if (B!=2) {for (int i=k; i>0; i--) {if (num[i]>1) { flag=i; break;}}for (int i=flag; i>=0; i--) {num[i]=1;} } for (int i=k;i>0; i--) {if (num[i]==1) {sum+=dp[i-1][need--];}elsecontinue; } return sum;}int main(int argc, const char * argv[]) { cin >> X >> Y; cin >> K >> B; dp[0][1]=0; dp[0][0]=1; dp[1][1]=1; dp[1][0]=1; handle(); Y=DP(Y+1); X=DP(X); cout << Y-X << endl; return 0;}``

Top