|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.02.2009, 15:29 | #1 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
За один ход можна вычеркнуть одно число и на его место записать строго меньше неотрицательное число.
Здравствуйте.
У меня есть такая задача: есть три целых числа a, b, c. Играют 2 участники. За один ход можна вічеркнуть одно число и на его место записать строго меньше неотрицательное число. Проиграет тот, хто не может сделать ход. Всегда первым ходит участник 1. Нужно вывести победителя (игрок 1 или 2) за данными начальными значениями a,b,c за условием что каждый участник будет использовать оптимальную стратегию. Например 3 4 5 Победитель : 1 Буду благодарен за любую помощь. Спасибо.
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
25.02.2009, 12:57 | #2 | |
Пользователь
Регистрация: 15.01.2009
Сообщений: 69
|
Решение задачи для одного и двух чисел
Цитата:
Во-первых, нельзя вычеркнуть «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-х чисел, как это было дано в задаче.
Silence is of great value...
|
|
25.02.2009, 14:13 | #3 | |
Пользователь
Регистрация: 15.01.2009
Сообщений: 69
|
Цитата:
Пусть имеем «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 Хм...
Silence is of great value...
|
|
25.02.2009, 16:06 | #4 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
Понятно, если можете, покажите немного в коде...
P.S. А почему вычеркивать 1 нельзя?
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. |
25.02.2009, 16:26 | #5 |
Пользователь
Регистрация: 15.01.2009
Сообщений: 69
|
А какое есть положительное число, менее 1?
Хотя, тут условие уточнить надо. «...вписать любое неотрицательное число» Тогда будет 0 у нас базовое. Но от этого ход рассуждений не меняется. Для одного числа проигрышной позицией будет 0, для двух числе — любая конструкция из двух равных чисел. Для трех чисел надо думать.
Silence is of great value...
Последний раз редактировалось Jean-Esther; 25.02.2009 в 17:54. |
25.02.2009, 17:44 | #6 |
Форумчанин Подтвердите свой е-майл
Регистрация: 27.04.2008
Сообщений: 179
|
Не можна вычеркивать 0, а 1 можна.
www.programmer.uaforums.net - Український форум програмістів.
www.satellite.ipsys.net - Український форум супутникового телебачення. Последний раз редактировалось Witaliy; 25.02.2009 в 17:44. Причина: Опечятка |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как в Label записать число в степени? | XilDen | Общие вопросы Delphi | 7 | 03.07.2009 21:03 |
Можно ли разделить сразу несколько цифр на одно и тоже число? | Xell | Microsoft Office Excel | 2 | 12.01.2009 13:32 |
Как записать число в двоичной форме? | Stellvertreter | Общие вопросы C/C++ | 2 | 16.10.2008 22:35 |
Число N, заменить одну из его цифр, чтобы получилось число, max близкое к некоторой степени двойки | urgu_st | Помощь студентам | 13 | 23.10.2007 09:14 |
Мне нужно выбрать данные из первого запроса, если он вернул хоть одно число=числу из | nata | Общие вопросы Delphi | 8 | 05.06.2007 23:57 |