Простое решение?

 

mansur115 | 2012-02-16 17:09:34 В этой задаче из состояния k, мы можем перейти вверх на 2 * k - 1, либо вниз на 2 * k - 1. Вниз переходить смысла нету, т.к. k - (2 * k - 1) = -k + 1, при любых k от 1 до N мы будем выходить за границу. Получается мы можем только сдвигаться вправо. Такое решение получается WA2. Подскажите я неверно понимаю условие?

 

ftc | 2012-02-16 18:00:59 Не совсем так. Дело вот в чём: изначально на шаге 1 человек пьёт, попадает в состояние 1 на шаге 2 пьёт, попадает в 4 на шаге 3 пьёт, попадает в 9 на шаге 4 не пьёт, попадает в 2 В этой ситуации человек оказывается в состоянии 2 на шаге 5, и если он будет пить, то попадёт в 11 (2 + (5 * 2 - 1)), а не в 5 (2 + (2 * 2 - 1))

 

mansur115 | 2012-02-16 19:59:01 А понял, не могли бы вы дать какую нибудь ссылку, или литературу где можно почитать про решение данной задачи?

 

ftc | 2012-02-16 20:08:19 Задача достаточно древняя, потому решения я не помню, но примерная идея выглядит так: если состояний небольшое количество (ну не более 1000), моно решить динамикой (в каком состоянии находимся, какой сейчас шаг) Если же их много, то можно доказать, что более-менее любое состояние будет достижимо (правда точную идею доказательства я не помню, увы)

 

Ответить.