Дед Мазай (Маzаj) и Заяц (Zayac) играют в очень простую игру. Перед ними гора из N одинаковых морковок. Каждый из игроков во время своего хода может взять из нее любое количество морковок, равное неотрицательной степени числа 2 (1, 2, 4, 8, ...). Игроки ходят по очереди. Кто возьмет последнюю морковку, тот и выигрывает. Составьте алгоритм, который при заданном значении V определяет победителя в этой игре. Учтите, что каждый из игроков хочет выиграть и не делает лишних ходов, т. е. играет оптимально.
Формат ввода
В первой строке имя игрока, который ходит первым: Mazaj или Zayac Во второй строке натуральное число N (1 < N < 1018)
Ответы
Ответ:
Ця гра відома як "гра в морковки", і вона може бути вирішена за допомогою математичних розрахунків. Вона базується на концепції "нормальної форми", де кожен гравець грає оптимально.
Правила гри дозволяють брати будь-яку кількість морквинок, що є степенем числа 2 (1, 2, 4, 8, ...). Основна ідея в тому, що якщо кількість морквинок, які залишилися, є степенем числа 2, то гравець, який ходить, може завжди взяти половину залишку, залишивши іншому гравцю степінь двійки (яка називається "позицією степеня двійки"). Тобто, якщо N - степінь двійки, то гравець, який ходить перший, завжди може виграти.
Отже, для визначення переможця:
Перевірте, чи N є степенем числа 2.
Якщо N є степенем числа 2, то перший гравець (той, хто ходить перший) переможе.
Цей алгоритм дозволяє визначити переможця за умови, що гравці грають оптимально та хочуть перемогти.
Объяснение: