ural 1353. Milliard Vasya's Function

ural 1353. Milliard Vasya's Function

點擊打開鏈接

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 digitsS. You seem to be great programmers, so Vasya gave you a task to find the milliard VF value (i.e. the VF with N = 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

Problem Author: Denis Musin
Problem Source: USU Junior Championship March'2005
在1~10^9這些數中，找出各個位數和為s的個數。 dp[i][j]表示位數為i的時候，各個位數之和為j的個數，那麼它是由兩部分組成，一部分是dp[i-1][j],因為可以在它的低位補0，另一部分是dp[i-1][j-k](1<=k<=9)，因為dp[i-1][j-k+k]就是dp[i][j]要求的。 感覺智商被碾壓~~

//0.031	206 KB
#include
#include
using namespace std;
int dp[10][107];
int main()
{
    int n,j;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=9;i++)dp[1][i]++;//從最高位往下找，最高位只能使1~9
    for(int i=2;i<=9;i++)
        for(int j=1;j<=81;j++)
        {
            dp[i][j]=dp[i-1][j];//第一部分
            for(int k=1;k<=9;k++)//第二部分
                if(j-k>0)dp[i][j]+=dp[i-1][j-k];
        }
    while(scanf("%d",&n)!=EOF)
    {
        int sum=0;
        if(n==1)printf("10\n");
        else
        {
            for(int i=1;i<=9;i++)//將各個位數符合條件的加起來
                sum+=dp[i][n];
            printf("%d\n",sum);
        }
    }
    return 0;
}