За один ход можна вычеркнуть одно число и на его место записать строго меньше неотрицательное число.

[Witaliy]

Здравствуйте.
У меня есть такая задача:
есть три целых числа a, b, c. Играют 2 участники. За один ход можна вічеркнуть одно число и на его место записать строго меньше неотрицательное число. Проиграет тот, хто не может сделать ход. Всегда первым ходит участник 1. Нужно вывести победителя (игрок 1 или 2) за данными начальными значениями a,b,c за условием что каждый участник будет использовать оптимальную стратегию.
Например
3 4 5
Победитель : 1
Буду благодарен за любую помощь.
Спасибо.

[Jean-Esther]

Сообщение от Witaliy

Здравствуйте.
У меня есть такая задача:
есть три целых числа a, b, c. Играют 2 участники. За один ход можна вычеркнуть одно число и на его место записать строго меньше неотрицательное число. Проиграет тот, хто не может сделать ход. Всегда первым ходит участник 1. Нужно вывести победителя (игрок 1 или 2) за данными начальными значениями a,b,c за условием что каждый участник будет использовать оптимальную стратегию.
Например
3 4 5
Победитель : 1
Буду благодарен за любую помощь.
Спасибо.

Ну-с, начнем разбор задачи (она, кстати, математического характера, нежели на программирование):
Во-первых, нельзя вычеркнуть «1»
Во-вторых, проигрывает тот, на чей ход выпадает «1 1 1 1 1 ... 1 1» — базовая проигрышная (для того, на чей ход она выпадает) либо выигрышная (если ходить в нее)
В-третих, положим у нас есть всего одно число (решаю в общем случае). Тогда в случае «1» мы проигрываем, так как не можем сделать ход, в противном случае ставим в позу соперника, делая «n»→«1».
В-четвертых, положим у нас два числа, ни одно не «1» (иначе сводим к п.3.), одно из них «2». Тогда если у нас «2 2», мы вдуваем, в случае «2 n» устраиваем подлость сопернику → «2 2».
В-четвертых, пусть есть два числа, одно из них «3», другое более «2». Тогда в случае «3 3» имеем... epic fail... хм... зато имея «3 n» можно завернуть какую-нибудь ставку (но тут от соперника зависит, думаю и 30$ деньги...).
В-пятых, имея «n m», в случае n=m получаем снова таки фейл, а если n<m, делаем «n n» и радуемся очередному выигрышу.
Пока вроде бы все правильно (исключая грамматику — тут я не силён). Сейчас перейдем до 3-х чисел, как это было дано в задаче.

[Jean-Esther]

Сообщение от Jean-Esther

Ну-с, начнем разбор задачи (она, кстати, математического характера, нежели на программирование):
Во-первых, нельзя вычеркнуть «1»
Во-вторых, проигрывает тот, на чей ход выпадает «1 1 1 1 1 ... 1 1» — базовая проигрышная (для того, на чей ход она выпадает) либо выигрышная (если ходить в нее)
...
В-пятых, имея «n m», в случае n=m получаем снова таки фейл, а если n<m, делаем «n n» и радуемся очередному выигрышу.
Пока вроде бы все правильно (исключая грамматику — тут я не силён). Сейчас перейдем до 3-х чисел, как это было дано в задаче.

Так вот, остановимся на трех числах «a b c». Установим порядок a≤b≤c. При этом a≠1.
Пусть имеем «2 2 2». Кто выиграет? Тот, кому позиция досталась.
Напомню, «2 2 1» — проигрышная позиция.
Значит, имея «2 2 а» при всех «а» сводим к выигрышной для нас ситуации «2 2 1». Радуемся.
Пусть имеем «2 3 3». Тогда спускаем «2» до «1» и смотрим за соперником. Аналогично, имея «k a a» всегда можем спустить до «1 а а» и тем самым поставить соперника в затруднительную ситуацию.
Пусть имеем «2 3 4». Тогда просмотрим варианты:
• «1 3 4» — fail («1 3 3»)
• «2 2 4» — fail («2 2 1»)
• «2 1 4» — fail («2 1 2»)
• «2 3 3» — fail («1 3 3»)
• «2 3 2» — fail («2 1 2»)
• «2 3 1» — fail («2 2 1»)
Как видно, во всех случаях нас ждет провал.
Теперь расширяем набор выигрышных позиций: «2 3 k», «2 k 4», «k 3 4».
Далее расмотрим «2 5 6»:
• «1 5 6» — fail («1 5 5»)
• «2 5 5» — fail («1 5 5»)
• «2 4 6» — fail
• «2 3 6» — fail
• «2 2 6» — fail
• «2 1 6» — fail («2 1 2»)
• «2 5 4» — fail
• «2 5 3» — fail
• «2 5 2» — fail
• «2 5 1» — fail
Хм...

[Witaliy]

Понятно, если можете, покажите немного в коде...
P.S. А почему вычеркивать 1 нельзя?

[Jean-Esther]

Сообщение от Witaliy

А почему вычеркивать 1 нельзя?

А какое есть положительное число, менее 1?
Хотя, тут условие уточнить надо.

«...вписать любое неотрицательное число»
Тогда будет 0 у нас базовое. Но от этого ход рассуждений не меняется.
Для одного числа проигрышной позицией будет 0, для двух числе — любая конструкция из двух равных чисел.
Для трех чисел надо думать.

[Witaliy]

Не можна вычеркивать 0, а 1 можна.