Задача:
https://cpp.mazurok.com/word-of-the-week/идём-к-ним/
Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины зерен, а так же для той задаче в которой максимальное съеденное число зерен задавалось пользователем. Я реализовал это достаточно просто: если m равна нулю во-второй задаче, то задача просто не имеет решения(как и смысла вообщем-то), именно поэтому я решил использовать нулевое m как показатель того что заданы параметры или для первой задачи.
|
1 |
if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n |
Вначале я воспользовался советом приложенным к задаче и расписал несколько вариантов в надежде заметить тенденцию и в последствии создать алгоритм который и будет находить ответ к задаче.
| Число зерен | Сколько нужно отнять зерен | Комментарий | Число зерен | Сколько нужно отнять зерен | Комментарий |
| 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]. тогда все что от нас требуется это найти найти такое число по этой формуле при котором количество зерен будет равно или меньше данного числа.
|
1 2 3 4 5 |
for( int i=1 ; r<n ; i++ ){ r++; r=r<<1; r--; // 2^i-1 } |
|
1 2 3 4 5 6 7 |
if ( r!=n ) // если существет выигрышный ход { r++; r=r>>1; // ... то мы находим 2^(i-1)-1 r--; } n-=r; // находим количество зерен которые нужно отнять |
Это все что касается первой задачи, но как оказалось вторая задача была совершенно аналогична:
Решение задачи я опять начал с расписывания нескольких вариантов, на этот раз если максимум съеденных зерен равен двум и соответственно трем:
| 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], а это значит что нам нужно всего лишь видоизменить алгоритм решения первой задачи просто подставив эту формулу вместо предыдущей.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <cstdlib> #include <iostream> using namespace std; int main() { int n, m, r=1; cin >> n >> m; if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n { --r; for( int i=1 ; r<n ; i++ ){ r++; r=r<<1; r--; // 2^i-1 } if ( r!=n ) // если существует выигрышный ход { r++; r=r>>1; // ... то мы находим 2^(i-1)-1 r--; } n-=r; // находим количество зерен которые нужно отнять if(!n)n=-1; } else // если введено m { while( r<n ){ r += m+1; //1+i*(m+1) } if( r!=n )r -= m+1; // если существует выигрышный ход, то возвращаемся к 1+(i-1)*(m+1) n -= r; // находим количество зерен которые нужно отнять if(!n)n=-1; } cout << n << endl; } |
К сожалению, выигрышных 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 неразрешимо в целых числах. Следовательно, формула, а с ней и решение, корректна в ограниченном числе случаев.
…->(II)->(2,1,2);
Нетрудно заметить, что первый игрок не может сделать следующий ход*
Что делает ваши доводы беспочвенными.
Перечитайте условие задачи, Вячеслав. Я думаю, вы обнаружите свою ошибку.
— Задача где можно есть не более половины, это частный случай второй задачи. Зачем их решать отдельно?
— m и n лучше оформлять в latex.
— Условие задачи 2 действительно стоит перечитать. С чего Вы решили, что можно есть не более m зёрен? Приведу цитату «не более m-й части оставшихся зёрен». Т.е. в задаче 1 не более половины (1/2), а в задаче 2 не боле 1/m.
— Ваш вариант задачи 2 тоже интересен.
Извиняюсь, видимо я неправильно понял условие задачи. В ближайшее время я исправлю этот недосмотр, и исправлю отчет.