ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1513. Басня о лимоне

Please help. Is my algo corect!?
Послано Lomir 17 янв 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?
Re: Please help. Is my algo corect!?
Послано KIRILL(ArcSTU) 17 янв 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],..)
Re: Please help. Is my algo corect!?
Послано Roma Labish[Lviv NU] 17 янв 2007 22:56
And you must to use long arithmetics...
Re: Please help. Is my algo corect!?
Послано Lomir 17 янв 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.
Re: Please help. Is my algo corect!?
Послано Todor Tsonkov 21 фев 2007 01:16
Can you say some clue about your DP, because mine gets TL on test 13, I use Java, btw.
Re: Please help. Is my algo corect!?
Послано Shyrik 26 сен 2007 19:42
F(n,1/0)
i - position
1 - limon
0 - banana
F(i,1) = sum(F(z,0));
F(i,0) = F(i-1,1)+F(i-1,0)