try think like dp[length of string][sum of string] = count of numbers, answer is dp[9][s].

-> think of doing this problem first -> count of n digits numbers whose sum is equal to x.
->First try to think for smaller numbers less than 1000 i.e from 1 to 999.
-> Create the tree for the same i.e numbers less than 999.
-> after finding f(n,sum)(n is the number of digits and sum is the required sum).
-> you can find f(9,sum)for all numbers less than 1000000000.
-> now finally you need to handle for one number 1000000000.
Cheers

Edited by author 31.07.2020 12:43

#include <stdio.h>
#include <map>
using namespace std;
int main() {
    int ans, sum, ost, s; long int full, i; map <long int, int> sums;
    for (i = 1; i <= 1000000000; i++) {
        sum = 0; full = i;
         do {
            ost = full % 10;
            full /= 10;
            sum += ost;
         } while (full > 0);
         sums[i] = sum;
    }
    for (s = 1; s <= 81; s++) {
        ans = 0;
        for (i = 1; i <= 1000000000; i++)
            if (sums[i] == s)
                ans++;
        printf("{%ld}, ", ans);
    }
}

it will give you {10}, {...}, ... , {...}, vector that you can use for getting AC with O(1).

Edited by author 11.03.2020 14:40

Edited by author 11.03.2020 14:44

Python 3
when counting by force I met TLE on the 45th test.
I printed out all the values of the function and saw that it is mirrored after 40 values.
f (40) = f (41)
f (39) = f (42)
...
f (2) = f (79)
therefore, counting only to 40, I got Accepted

just be patient while making precalculation :)

I am not able to understand the problem properly. Is there somebody who can explain the problem with example. Pls

Edited by author 21.11.2018 16:56

Edited by author 21.11.2018 16:57

I thought that this problem is so easy. After many tries to solve that I should say: that is not so easy and I cant solve it! Please, if you DP-master tell me where I'm wrong.

So, the state is dp[sum][length] += dp[sum - digit][length - 1], for each digit 0..9. The base is dp[1..9][1] = 1.

I've got WA#10:
My program for 10 output: 43756 (correct answer: 43749)

I can't find a little bug ;(

Recursive solution works fine! If you are getting TLE, Rethink your DP state :)

Let your recursion function is "void dfs1(int k, int curr)", k is digit, curr is current S, then use it code:

    int start = 0;
    start = max(start, curr - 9 * (k - 1));

    int end = min(9, curr);
    if(k == 10) {
        end = min(1, end);
    }

    for(int i = start; i <= end; i++) {
        dfs1(k - 1, curr - i);
    }

It turns out, curr does not go beyond zero at k = 0!
I have 937ms with this solution

But with precalc I have 31ms :)
Good luck

Hi Can anybody help me to convert my recursive solution to iterative. Can i Post code here?

You can solve it o(1) just precalc answers fir all test by brute forse, than put it to array.
Proffit

Ok, so my program gets WA2. And if I add code like
int t2=45;
if(n==2) cout << t2 << endl;
I get WA3. Funny fact though - "45" is answer my program always gave for n==2. So we have two different "45", and only one of them is good as answer. Somehow cout << s(9,n) << endl; doesn't work well, even if s(9,n)=45. Someone had problems of this kind?

It's not the easiest problem and I don't know good solution, but if I was on the olympiad and would have to solve the problem, I would just precalculate the answer.

What's wrong with 33th test?))
Or what reazons to access violation?

My program gives the following answers:
1  -> 10
2  -> 45
3  -> 165
10 -> 43749
40 -> 45433800
80 -> 9
81 -> 1

Why do I get WA1?

Edited by author 13.07.2012 14:17

If you have program which gives right answer for the problem, but it's too slow and gets TLE, then you may just calculate answers for every possible input(there are only 81 possible variants of input, so you can calculate them all) and then create another program: put array of 81 possible answers in this program and them just read s from input and write in output corresponding answer from the array.
I had made such program and it got AC.

I can't understand my mistake(

mem[1][9] <=> 1=>>10
mem[20][9] <=> 20=>>299 or 29 ?