Задача Простая игра

ПРОСТАЯ ИГРА.
Дед Мазай и заяц играют в очень простую игру. Перед ними огромная куча одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8, … Начинает игру либо Дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.
Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.

Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит единственное целое число N (N10250), задающее число морковок в начале игры.

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать в первой строке цифру «1», если выиграет тот, кто ходит первым, или цифру «2» - в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.

Пример файлов входных и выходных данных:
INPUT.TXT OUTPUT.TXT
8 1
2

Указания к решению.
В этой игре 2 игрока делают ходы по очереди, и выигрывает тот, кто достигает некоторой намеченной в начале игры позиции. В данной игре позиция
может быть полностью охарактеризована числом оставшихся морковок, и выигрывающая позиция соответствует числу морковок, равному нулю.
Спраг и Грюнди предложили (соответственно в 1936 и 1939 годах) связывать с каждой игровой позицией неотрицательное число следующим образом:
1) выигрывающей позиции сопоставляем 0;
2) данной игровой позиции сопоставляем наименьшее неотрицательное целое, отличающееся от чисел, связанных с позициями, которые могут быть достигнуты, исходя из данной.
Образуем числа Спрага-Грюнди (SG) для этой игры:
• позиции 0 сопоставляем число 0, т.е. SG(0)=0;
• исходя из 1, можно получить 0 (поскольку мы имеем право взять одну морковку). Следовательно, SG(1) – наименьшее неотрицательное целое число, отличное от нуля, т.е. SG(1)=1;
• исходя из 2, можно получить 0 и 1. Значит SG(2) – наименьшее неотрицательное целое число, отличное от 0 и 1, т.е. SG(2)=2;
• пусть у нас имеется 3 морковки. Можно взять 1 или 2, в результате чего останутся 2 или 1 морковка, но не 0. Число SG(3) – наименьшее неотрицательное целое число, отличное от 1 и 2, т.е. SG(3) =0;
• из 4 можно получить позиции 0, 2 или 3 (если взять соответственно 4, 2 или 1 морковку). Следовательно SG(4) – это не 0 и не 2, значит SG(4)=1;
• из 5 получаем позиции 1, 3 или 4. Значит SG(5)=2.
Установим общий закон: SG(p) есть остаток от деления p на 3.
Теперь осталось выявить стратегию (кто выигрывает) и соотнести полученный алгоритм с ограничениями на входные данные (N10250).

Контрольные тесты
INPUT.TXT OUTPUT.TXT
2733591 2
10000000000000000 1
1
100000000000000002 2
452837423623687234663 1
1

1

мне тоже очень нужна эта задача

1

Сообщение от инна_ мне тоже очень нужна эта задача

нужна для чего, если не секрет?

2

все просто,чтобы сдать программирование

1

1