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

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 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 ;(

If you are using recursion function to calc the answer, then I suggest you to do it in one of some ways:

1) To write DP without using recursion.
2) To use array of memory and put there -1 if we calced the function of this parametres and 0 if not.
3) if you write in C++, inline may be will help you.

If you have any questions, write.

Edited by author 19.11.2010 01:08

I use a simple DP ,but WA#10.Give me some useful tests,pls.
And I'd like to know if there is a better algo.

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

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

what is 11 test? I think I checked everything possible variants? can you help me?

Cos My English is Bad
I don't Understand this Problem

PS. Thank you

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

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.

My source is consisted of 8 cycles from zero to nine and one counting and works for 0.356 or something like that.

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