|
|
|
|
|
|
|
Вернуться
| 1 Сокол Константин Иванович, 16 декабря 2010 г. 21:48:40 | |
|
понимаю, сам долго с этой задачей мучался (accept +8 говорит о много=)))
|
|
|
| 2 Демиденко Виталий, 16 декабря 2010 г. 15:50:16 | |
|
Да, я понял, что ты хотел сказать, но прикол в том, что в условии ни слова не сказано ни про идеальную игру, ни про стратегии, ни про выигрышные/проигрышные позиции...
|
|
|
| 3 Сокол Константин Иванович, 16 декабря 2010 г. 8:41:54 | |
|
из меня рассказщик конечно не очень, но попробую: фишка этого жадника заключается в том что я не писал ДП ,а просто листике сам себе доказал, что гарантированно можно придти только в центр. Причем если у нас нечётное s, то по теории шпрага-гранди мы в заведомо проигрышной позиции. Мы можем свести игру в лучшем случае в две клетки(которые нах-ся под (s div 2) и (s div 2 + 1)). Тк последний ход соперника, то он выберет наименьшее значение из предложенных двух(из той позиции куда мы его привели). Если у нас четное s, то уже мы находимся в выйграшной позиции, Мы можем свести игру в лучшем случае в одну клетку(которая под (s div 2)). Оттуда мы ,разумеется, выберем максимальную. Надеюсь объяснил
|
|
|
| 4 Демиденко Виталий, 16 декабря 2010 г. 5:31:14 | |
|
А ты можешь совместить это решение с условием задачи?
|
|
|
| 5 Сокол Константин Иванович, 15 декабря 2010 г. 20:22:08 | |
|
просто если знаешь решение то сразу становится понятным первый(да и все) тесты. Рассказывать как там получилось 5 равносильно тому что я написал
|
|
|
| 6 Демиденко Виталий, 15 декабря 2010 г. 19:18:30 | |
|
а кто-то решение просил рассказывать?
|
|
|
| 7 Сокол Константин Иванович, 15 декабря 2010 г. 17:44:53 | |
там если s = 1 тогда ans = a[1];
если s - четное, то ans = max(a[s div 2],a[(s div 2)+1]);
если s - нечетное, то ans:=min(a[(s div 2)+1],max(a[s div 2],a[(s div 2]+2]));
|
|
|
| 8 Павел Борсук Аллександрович, 15 декабря 2010 г. 15:39:11 | |
|
кстати в условии 5 задачи скрыто решение одной задачи из прошлых олимпиад)
|
|
|
| 9 Jazzy, 15 декабря 2010 г. 13:17:20 | |
|
i men9
|
|
|
| 10 Генадий Врублёвский, 15 декабря 2010 г. 12:53:28 | |
|
Меня тоже интересует этот вопрос
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
