ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1803. The Czechs' Rifles

Solving
Posted by Vasiliy 31 Oct 2010 16:56
Could you please give me a hint?
Do we need to generate a fibonachi digits in any way or there is a better solution?
Re: Solving
Posted by quick(YarSU) 31 Oct 2010 19:37
same question.
I wrote the solution:
1) generate fib one by one and sum digits.
2) very optimize actions and no copy array of digits
3) stable sort or count sort

==>

it works on test "2 50000" about 4 - 5 second.
TL 12
How did you avoid TL?
Re: Solving
Posted by Moonstone [Samara SAU] 1 Nov 2010 09:56
1. Generate all sums of digits for numbers from 0 to k^p-1 (the best p is 6 for my solution)
2. Replace k with k^p
3. Run stupid solution but add precalculated numbers to sum
4. ???????
5. PROFIT
Re: Solving
Posted by quick(YarSU) 1 Nov 2010 12:41
accepted...
Re: Solving
Posted by 72VanVector[SevNTU] 4 Nov 2010 20:50
How can i generate Fibonchi num 50000? it is very big!
Re: Solving
Posted by Moonstone [Samara SAU] 4 Nov 2010 22:48
Use long arithmetics.
Re: Solving
Posted by 72VanVector[SevNTU] 5 Nov 2010 01:57
So in the worst case i must calculate the 50000 Fibonachi numbers, writing them using long arithmetic, at the same time calculating the number of banknotes to pay for them, writing this calculations in separate array. Then i must sort this array and print the bounded numbers of sorted elements from begin to the end.

Is this method ok?
Re: Solving
Posted by Moonstone [Samara SAU] 5 Nov 2010 13:57
This method gets TLE, but it may be improved (look at my previous messages).
Re: Solving
Posted by 72VanVector[SevNTU] 5 Nov 2010 14:52
Thx... Will try to calculate the number of banknotes using precounted values...
Re: Solving
Posted by Vasiliy 8 Nov 2010 01:26
Guys, could you please send me your code for investigation?
kobchik83@list.ru
Re: Solving
Posted by elkasimi 4 Dec 2010 21:47
THANKS A LOT FOR YOUR HINT !!
Re: Solving
Posted by elkasimi 4 Dec 2010 21:51
THANKS A LOT FOR YOUR HINT !!
Re: Solving
Posted by elkasimi 4 Dec 2010 21:53

Edited by author 04.12.2010 21:54