Задача №114032. Нечетный ним
Миша и Глеб очень любят знаменитую игру ним. Напомним вкратце её правила:
- На столе лежат N кучек камней, в кучке с номером i содержится a i камней.
- Играют два игрока, игроки ходят по очереди, на каждом ходу игрок обязан выбрать любую непустую кучку и убрать из неё любое ненулевое количество камней.
- Проигрывает тот, кто не может сделать ход.
Наши герои играют в эту игру уже так давно, что обнаружили выигрышную стратегию, и теперь могут определить победителя просто взглянув на стол. Поняв, что данная игра утратила свою новизну, они переключились на ним в поддавки, который отличается от оригинального только тем, что игрок, который не может сделать ход, объявляется победителем.
Друзья весело проводили долгие вечера за этой новой забавой, пока не пришел Витя и не рассказал им, что исход данной игры так же можно предсказать лишь взглянув на стол.
Тогда было принято решение еще усложнить правила — теперь разрешается брать только любое нечетное количество камней. На этот раз Витя не смог обнаружить стратегию и помешать двум друзьям, поэтому он обратился за помощью к вам. Напишите программу, определяющую победителя в игре ним, если разрешается брать из кучки только нечетное количество камней. На всякий случай научитесь также определять победителя для нима в поддавки, в котором также можно брать только нечетное количество камней — Витя подозревает что именно эта игра станет для Глеба и Миши следующей.
Миша всегда ходит первым.
В первой строке входного файла записано единственное число N , 1 ≤ N ≤ 10 5 . Следующая строка содержит N чисел a i , 1 ≤ a i ≤ 10 9 .
На первой строке выведите имя победителя в том случае, если проигрывает тот, кто не может сделать ход. Во второй строке выведите имя победителя в том случае, если тот, кто не может сделать ход, выигрывает.
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, эта группа оценивается в ноль баллов.
- Тесты 2–15. В тестах этой группы N ≤ 3, a i ≤ 6 . Эта группа оценивается в 20 баллов.
- Тесты 16–24. В тестах этой группы N ≤ 5, a i ≤ 10 . Эта группа оценивается в 20 баллов.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 60 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
2 1 2
Misha Gleb