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 1513. Lemon Tale

Posted by Lomir 17 Jan 2007 21:16
Is my algo correctm or it's defenetely wrong?
Firstly, i count all possible changes 2^n.
Then i withdraw changes which do not siunt the censor (by fixing k+1 not changed lemons). Later i fix k+2 (one banana and k+1 lemons) and count new unsiutable chages.

res = 2^n;
res = res - 2^(n-k-1);
for (int i = 0; i <= k && i+k+1<n; ++i)
{
int t = n - k - 2;
if (t<0)
break;
res = res - 2^t;
}

I've got WA9, so this is cause my algo or my implementation? :)

P.S. Nothing to change, then n==k, also must be counted or not?
Posted by KIRILL(ArcSTU) 17 Jan 2007 21:29
This problem like a 1009 (k=2)
Solution - dp
try to find f[n] through previous values(f[n-1],f[n-2],..)
Posted by Roma Labish[Lviv NU] 17 Jan 2007 22:56
And you must to use long arithmetics...
Posted by Lomir 17 Jan 2007 23:43
Thant for clue. Now I got AC.
Java's BigInteger and none need for long arithmetic.

Mine first algo was wrong, it's need about 2 cicles with minus more to be correct.