1353. Milliard Vasya's Function

Time limit: 1.0 second
Memory limit: 64 MB

Vasya is the beginning mathematician. He decided to make an important contribution to the science and to become famous all over the world. But how can he do that if the most interesting facts such as Pythagor’s theorem are already proved? Correct! He is to think out something his own, original. So he thought out the Theory of Vasya’s Functions. Vasya’s Functions (VF) are rather simple: the value of the Nth VF in the point S is an amount of integers from 1 to N that have the sum of digits S. You seem to be great programmers, so Vasya gave you a task to find the milliard VF value (i.e. the VF withN = 109) because Vasya himself won’t cope with the task. Can you solve the problem?

Input

Integer S (1 ≤ S ≤ 81).

Output

The milliard VF value in the point S.

Sample

input	output
1	10

A simple iterative / recursive dp(recommended ) can give the answer.

The state of the DP is dp[digit][sum] which stands for the number of ways of constructing number with d digits such that sum is S;

 **** into the solve function

the solve function is called with solve(9,sum)

as the number of digits need to be 9

now the 3 steps are 

if(sum<0)

then there are no ways so we return 0.

if(d==0)

{

    if(sum==0) then there is 1 way as we have exhausted all the numbers and sum has returned to zero

    else there is no way

}

else we place digits from (0 to 9  for(int i=0;i<=9;i++) and add it to dp[d][s];

 the recursive step is dp[d][s]+=dp[d-1][s-i] i.e putting the ith digit in the dth position we go backward.

*****  here is the code    ****

#include<iostream>

#include<stdio.h>

using namespace std;

long long int dp[11][100];

int solve(int d, int s)

{

if(s<0)

return 0;

if(d==0)

{

if(s==0)

return 1;

else

return 0;

}

if(dp[d][s]!=-1)

return dp[d][s];

else

{

dp[d][s]=0;

for(int i=0;i<=9;i++)

{

dp[d][s]+=solve(d-1,s-i);

}

    }

    return dp[d][s];

}

int main()

{

//int dp[10][100];

for(int i=0;i<=10;i++)

{

for(int j=0;j<=83;j++)

dp[i][j]=-1;

}

int S;

cin>>S;

long long int val=solve(9,S);

if(S==1)

{

cout<<val+1<<endl;

}

else

cout<<val<<endl;

return 0;

}