|
|
back to boardRe: 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 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 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 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 > 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 thank you for idea that increasing order idea Re: Increasing order This problem has simple brutforce solution. Just sum all numbers from 1 , while sum <= n Re: Increasing order 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 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 |
|
|