Показать сообщение отдельно
  (#1 (permalink)) Старый
Anonymous
Guest
 
Сообщений: n/a
По умолчанию Помогите с решением задачи с выходным файлом INPUT.TXT - 24.02.2003, 06:36

срочно нужно решить задачку... помогите, please...
"Простая игра"
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест.
Ученики школы Хогварц любят играть в очень простую игру. Играют два человека. Перед ними – огромная куча из N волшебных палочек. Каждый из игроков во время своего хода может взять из этой кучи любое количество палочек, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8,… . Игроки ходят по очереди. Тот, кому достанется последняя палочка, тот и выигрывает.
Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.
Формат входных данных:
Входной файл INPUT.TXT содержит единственное целое положительное число N (N≤10^250), задающее число волшебных палочек в начале игры.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать в первой строке цифру ‘1’, если выиграет тот, кто ходит первым, или цифру ‘2’ – в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число палочек, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.
Пример файлов входных и выходных данных:
INPUT.TXT OUTPUT.TXT
8 1
2

если из k спичек можно брать от одной до n спичек, то нужно стремиться оставлять после своего хода кратное (n+1) число спичек, а на ход противника, взявшего k спичек, нужно отвечать взятием (n-k) спичек.
Тут дела обстоят по-другому. Судя по всему, после своего хода следует оставлять такое количество спичек, чтобы: а) из следующий игрок не мог забрать сразу; б) после любого хода следующего игрока, можно было бы забрать все оставшееся или опять взять как-нибудь по-хитрому.
Все это дело никак не могу сообразить в виде формул, а, следовательно, и в виде алгоритма.
Что делать с этим всем?
Ответить с цитированием
Ads