|
|
|
|
|
|
|
| 1 Пальчесвкий Максим Дмитриевич, 10 декабря 2024 г. 11:38:42 |
| Подскажите, пожалуйста, кто должен выиграть в такой ситуации? 8 5 4 3 2 1 1 2 3
|
|
|
| 2 Ягияев Игорь, 09 сентября 2021 г. 23:14:24 |
| Спасибо за задачу! Она меня чуть не победила! ДП - это динамическое программирование
|
|
|
| 3 Гаврилов Максим Сергеевич, 25 февраля 2021 г. 18:55:30 |
| Админ, подскажите, пожалуйста, где прочитать, узнать, что такое ДП и с чем его едят. Просто совсем не лажу с этой темой, но очень хочу разобраться, пишу я на Python. Просто вчера часа полтора по инету лазал, но так ничего понятного так и не нашёл :( Заранее спасибо!
|
|
|
| 4 Уфимцев Сергей Александрович, 05 мая 2020 г. 7:26:21 |
| Ребят, не тупите, там первый берет 3 второй 4 потом первый берет 5 и уходит в стратосферу
|
|
|
| 5 Белозерский, 24 апреля 2020 г. 13:08:29 |
| В первом тесте на первом ходу первый игрок будет брать цифру 3, а не 4, чтобы выиграть.
|
|
|
| 6 Стрелецкий Павел Константинович, 08 апреля 2020 г. 14:54:45 |
| Как в 1 тесте ответ получился 1? Блин, да здесь логично что игра будет такая: 3 2 5 4 - 1 игрок берёт число 4, оно удаляется. 3 2 5 - 2 игрок берёт число 5, оно удаляется. 3 2 - 1 игрок берёт число 3, оно удаляется. 2 - 2 игрок берёт число 2, оно удаляется. Получается, 1 игрок собрал числа 4 и 3; 2 игрок собрал числа 5 и 2. Тогда посчитаем сумму: 4 + 3 = 7 5 + 2 = 7, суммы равны, => ответ 0 - ничья. Как, Админ, вы получили ответ 1?)
|
|
|
| 7 АЩщщ, 07 февраля 2020 г. 16:19:30 |
| Очень хорошая задача.
|
|
|
| 8 Кудрин Максим Витальевич, 07 января 2020 г. 20:54:23 |
| Можно очки первого игрока брать положительными, второго - отрицательными. В конце если сумма положительна - то выиграл первый, отрицательна - второй, 0 - ничья. Сначала решил рекурсией - 6 тест по времени не прошел. Еле додумал до оптимального решения
|
|
|
| 9 Петухов Алексей Владимирович, 16 марта 2019 г. 20:09:34 |
| Спойлер: dp[start][end][last], если last == 2 - ходил второй, иначе первый(сейчас ход первого и второго соответственно). Первый пытается максимизировать значение dp, второй - минимизировать.
|
|
|
| 10 Николай, 31 августа 2018 г. 14:59:19 |
Самая интересная задача на дп, которую я решал. Спасибо автору. Еще бы не помешало восстановление ответа.
В играх плохо восстанавливать ответ, потому что играют двое, и противник вообще говоря играет непредсказуемо. Максимум что можно сделать в такой ситуации - если выиграет первый игрок, попросить указать первый ход, приводящий к выигрышу.
|
|
|
| 11 Глубокий Станислав Сергеевич, 23 августа 2016 г. 20:37:04 |
| Ребята, не пытайтесь найти какие-то правила оптимальной игры. Это ДП, которое (по крайней мере, у меня) сводится к тому, что игрок перед ходом должен знать, сколько он наберет очков, если выберет правый/левый элемент. Надо сравнить сумму очков, которую игрок наберет к концу игры при выборе правого элемента, и сумму очков, которую он наберет к концу игры при выборе левого элемента. Где сумма больше, так ходить и надо.
|
|
|
| 12 Баянов В В, 16 июня 2015 г. 12:27:10 |
| Задача интересная. но не очень сложная и никак не тянет на межнар, (была предложена в 1996 году на межнар олимпиаде), хотя и была самой первой, то есть одной из самых простых.
|
|
|
| 13 Бальзин Егор, 19 марта 2015 г. 21:36:24 |
Внимание: спойлеры!!!
ans[i][j] - максимальное кол-во денег которое можно набрать в кучках с i-ой по j-ую.
|
|
|
| 14 ЛУффи, 17 февраля 2015 г. 9:50:16 |
| Легче всего решить через динамику по подотрезкам
|
|
|
| 15 Васильев Владислав Вячеславович, 09 января 2012 г. 0:15:13 |
а как называется эта игра???
Она без названия, поэтому "Игра - 2" :)
|
|
|
| 16 Кравцов Дмитрий, 03 сентября 2010 г. 19:22:00 |
Скажите пожалуйста, можно ли решить рекурсией эту задачку?
Можно, только не полным перебором. Здесь подойдет нисходящая динамика.
|
|
|
| 17 Зубашев Степан, 18 ноября 2009 г. 23:40:28 |
вах вах! я таки сдал этого монстра =) оказывается всё эти закономерности которые тут люди (в том числе) и я выводили нафиг не нужны.
подсказка тем кто долго мучается и как я ничего не понимает в ДП:
1 напишите перебор, которые решает все тесты (тл не в счёт)
2 добавте в этот перебор возможно запоминать наилучший выбор (слева взять цифру или справа) для игрока (например int mas[100][100], где mas[start,end] будет хранить наилучший выбор в такой последовательности), и каждый раз натыкаясь в рекурсиях на уже известное растояние не лезть внутрь рекурсии, а брать ответ из этого массива
надеюсь доступно обьяснил. думаю админ именно это имел ввиду когда писал что надо использовать двумерные массивы
да, я имел ввиду именно это. у вас как раз идеи на рекурсивную реализацию нисходящей динамики. программа еще более эффективно работает, если реализовывать восходящую динамику без рекурсии, двойным циклом: получается код короче, работает быстрее, но думать надо чуть-чуть больше. мне тоже кажутся рекурсивные реализации проще, т.к. не приходится задумываться о последовательности вычислений значений.
|
|
|
| 18 Набиев Умед (ТРГИ), 18 сентября 2009 г. 13:49:22 |
админ скажите пж в каждом ходе игрок должен выбирать макс из двух краев?
не всегда выбор максимального с краю приводит к победе
|
|
|
| 19 Kuzmin Alexey Andreevich, 14 января 2009 г. 19:33:45 |
Слабенько для IOI... А почему бы не выводить в этой задаче разницу между счетами 1го и 2го? Задача особо не меняется, то же ДП по подстрокам, но тестить легче (для человека :-) ) Кстати у Вас в условии не сказано, чего же должно быть в сумме больше у победителя. Это конечно и так ясно, но...
Думаю, что самое простое в этой задаче - это догадаться чего больше надо набрать первому игроку ;)
|
|
|
| 20 Сушенцев Игорь, 29 ноября 2008 г. 16:20:49 |
А мне интересно, у Вас в решении используются двумерные массивы?
У меня лично да, вроде как так попроще. Это как-никак нисходящее ДП.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
