Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


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

надеюсь доступно обьяснил. думаю админ именно это имел ввиду когда писал что надо использовать двумерные массивы
     да, я имел ввиду именно это. у вас как раз идеи на рекурсивную реализацию нисходящей динамики. программа еще более эффективно работает, если реализовывать восходящую динамику без рекурсии, двойным циклом: получается код короче, работает быстрее, но думать надо чуть-чуть больше. мне тоже кажутся рекурсивные реализации проще, т.к. не приходится задумываться о последовательности вычислений значений.
  16  Набиев Умед (ТРГИ), 18 сентября 2009 г. 13:49:22
     админ скажите пж в каждом ходе игрок должен выбирать макс из двух краев?
     не всегда выбор максимального с краю приводит к победе
  17  Kuzmin Alexey Andreevich, 14 января 2009 г. 19:33:45
     Слабенько для IOI... А почему бы не выводить в этой задаче разницу между счетами 1го и 2го? Задача особо не меняется, то же ДП по подстрокам, но тестить легче (для человека :-) ) Кстати у Вас в условии не сказано, чего же должно быть в сумме больше у победителя. Это конечно и так ясно, но...
     Думаю, что самое простое в этой задаче - это догадаться чего больше надо набрать первому игроку ;)
  18  Сушенцев Игорь, 29 ноября 2008 г. 16:20:49
     А мне интересно, у Вас в решении используются двумерные массивы?
     У меня лично да, вроде как так попроще. Это как-никак нисходящее ДП.
  19  Сушенцев Игорь, 29 ноября 2008 г. 16:18:15
     Блин, само решение(причем соблюдая структуру) < 15 строк, а проходит!
  20  Умед, 11 ноября 2007 г. 8:57:19
     Зачем врать?! Эта задача была на Международной олимпиаде в 96 году! и Степанов правильно сказал.
     Я не вру, что я ее придумал. Просто часто придумываешь "велосипед". Наверное, не сложная задачка для международной олимпиады-то...
 1 2

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru