I compose n from sums of digits of the numbers:
99999 (sum of digits = 45)
99998 (44)
99997
.....
99990 (36)
99989 (44)
.....

until i gain total sum of digits = n.
I take the numbers in such an order because the greatest sums (in average) are in that part of valid range.

I suppose you can start from little numbers but i didn't try.

Increasing order causes WA#6.

More funny solution without WA:
use n for n and so on(recursively)

It is even enough to start from n, not from 99999.

I guess in that case the solution will be more generic, it'll work for any positive n.

Edited by author 04.04.2010 17:06

here is my way to solve this problem:
1. count sum of digits for every number from 1 to 99999
2. sort then
3. find some unmarked close number and add it to the answer(with binary search)
4. n=n-a[number] =)
that's all
btw there is no "-1" answer

Just take n and decrease it by it sum of digits, keep doing this until n = 0

> Increasing order causes WA#6.

But why?!
However, decreasing order is more greedy, but still don't know why it works.

p.s. also got 0.046s AC with 100% solution using map<int,list<int>,greater<int> > container and its lower_bound method.

Edited by author 27.10.2011 05:53

thank you for idea that increasing order idea

This problem has simple brutforce solution. Just sum all numbers from 1 , while sum <= n

Me too.I use c++ because of it's STL, use multimap can slove it

Edited by author 11.11.2012 18:00

First observation we need to make is to see that the highest sum of digits within 10^5 has the number "99999" and it's value is 45. This means that if the input number of digits is more or equal than 45 we can use any number and it will always fit.

We want to make everything quickly so it's best to start from numbers with a lot of nines in them.

99999 (sum = 45)
99998 (sum = 44)
...
96742 (sum = 28)
96741 (sum = 27)

We subtract the sum one by one until we are left with a number of digits that's lower than 45.

Second observation is to see that 9+8+7+6+5+4+3+2+1=45 and that there always is a combination of 9,8,7,6,5,4,3,2,1 that You can sum up to any number lower or equal to 45.

That way we end up with something like this:
Input: 55
3
99999 9 1

Edited by author 12.07.2016 19:56