WoW 3. Идем к ним?

Задача:
http://cpp.mazurok.com/word-of-the-week/идём-к-ним/

Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины зерен, а так же для той задаче в которой максимальное съеденное число зерен задавалось пользователем. Я реализовал это достаточно просто: если m равна нулю во-второй задаче, то задача просто не имеет решения(как и смысла вообщем-то), именно поэтому я решил использовать нулевое m как показатель того что заданы параметры или для первой задачи.

Вначале я воспользовался советом приложенным к задаче и расписал несколько вариантов в надежде заметить тенденцию и в последствии создать алгоритм который и будет находить ответ к задаче.

Число зерен Сколько нужно отнять зерен Комментарий Число зерен Сколько нужно отнять зерен Комментарий
1 0 П 9 2 В
2 1 В 10 3 В
3 0 П 11 4 В
4 1 В 12 5 В
5 2 В 13 6 В
6 3 В 14 7 В
7 0 П 15 0 П
8 1 В

В — Выигрышный вариант существует
П — Нет выигрышного варианта

Исходя из выше описанной таблицы вполне ясно виден алгоритм, так как выигрышный вариант отсутствовал только в случаях, где число зерен соответсвовало данной формуле: [latex]{ 2 }^{ n }-1[/latex]. тогда все что от нас требуется это найти найти такое число по этой формуле при котором количество зерен будет равно или меньше данного числа.

Если изначальное число зерен будет меньше полученного числа, то выигрышный вариант существует и все что от нас требуется, так это найти предыдущее число ( иными словами нужно найти [latex]{ 2 }^{ n-1 }-1[/latex]) и узнать сколько же зерен нужно отнять чтобы сделать выигрышный ход:

Это все что касается первой задачи, но как оказалось вторая задача была совершенно аналогична:
Решение задачи я опять начал с расписывания нескольких вариантов, на этот раз если максимум съеденных зерен равен двум и соответственно трем:

2 3
Число зерен Сколько нужно отнять зерен Комментарий Число зерен Сколько нужно отнять зерен Комментарий
1 0 П 1 0 П
2 1 В 2 1 В
3 2 В 3 2 В
4 0 П 4 3 В
5 1 В 5 0 П
6 2 В 6 1 В
7 0 П 7 2 В

Как вы могли уже заметить здесь тоже можно заметить очевидную тенденцию, в которой выигрышного варианта нет в тех случаях, когда число зерне соответствует этой формуле [latex]1+i(m+1)[/latex], а это значит что нам нужно всего лишь видоизменить алгоритм решения первой задачи просто подставив эту формулу вместо предыдущей.

Куленюк Денис Віталійович
Куленюк Денис Віталійович

Latest posts by Куленюк Денис Віталійович (see all)

6 thoughts on “WoW 3. Идем к ним?

  1. К сожалению, выигрышных n куда больше, чем тех из них, которые описываются по формуле 1+i*(m+1) для натуральных i. При n = 5, m = 3 существует выигрышная последовательность (к слову, единственно возможная):
    (0, 5, 0) -> (I) -> (1, 4, 0) -> (II) -> (1, 3, 1) -> (I) -> (2, 2, 1);
    Нетрудно заметить, что второй игрок не может сделать следующий ход, а уравнение
    1+4*i = 3 неразрешимо в целых числах. Следовательно, формула, а с ней и решение, корректна в ограниченном числе случаев.

  2. — Задача где можно есть не более половины, это частный случай второй задачи. Зачем их решать отдельно?
    — m и n лучше оформлять в latex.
    — Условие задачи 2 действительно стоит перечитать. С чего Вы решили, что можно есть не более m зёрен? Приведу цитату «не более m-й части оставшихся зёрен». Т.е. в задаче 1 не более половины (1/2), а в задаче 2 не боле 1/m.
    — Ваш вариант задачи 2 тоже интересен.

Добавить комментарий