ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1727. Znaika's Magic Numbers

plz give me any hint
Posted by Michail Yudin 17 Oct 2009 19:50
Re: plz give me any hint
Posted by melkiy 18 Oct 2009 00:15
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
Posted by Partisan 19 Oct 2009 22:13
Increasing order causes WA#6.
Re: Increasing order
Posted by svr 20 Oct 2009 02:08
More funny solution without WA:
use n for n and so on(recursively)
Re: plz give me any hint
Posted by burdakovd 4 Apr 2010 17:00
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
Re: plz give me any hint
Posted by Roman Rubanenko 4 Apr 2010 23:46
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
Re: plz give me any hint
Posted by MarioYC 24 Sep 2011 12:18
Just take n and decrease it by it sum of digits, keep doing this until n = 0
Re: Increasing order
Posted by luckysundog 27 Oct 2011 05:43
> 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
Re: Increasing order
Posted by panther.uz 21 Sep 2012 02:56
thank you for idea that increasing order idea
Re: Increasing order
Posted by Andrew Sboev [USU] 21 Sep 2012 20:16
This problem has simple brutforce solution. Just sum all numbers from 1 , while sum <= n
Re: Increasing order
Posted by Pegasus 7 Nov 2012 19:48
Me too.I use c++ because of it's STL, use multimap can slove it

Edited by author 11.11.2012 18:00
Re: plz give me any hint
Posted by Filip Franik 12 Jul 2016 19:54
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