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

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

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

How can i generate Fibonchi num 50000? it is very big!

Re: Solving

Use long arithmetics.

Re: Solving

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

This method gets TLE, but it may be improved (look at my previous messages).

Re: Solving

Thx... Will try to calculate the number of banknotes using precounted values...

Re: Solving

Guys, could you please send me your code for investigation?

kobchik83@list.ru

Re: Solving

THANKS A LOT FOR YOUR HINT !!

Re: Solving

THANKS A LOT FOR YOUR HINT !!

Re: Solving

*Edited by author 04.12.2010 21:54*