Codeforces Round 188 (Div. 1) |
---|
Закончено |
Вася и Петя выписали на доску все натуральные числа от 1 до n и играют в игру (n может быть достаточно велико, но Васю и Петю это не смущает).
Игроки по очереди выбирают числа, начинает Вася. Если на данном ходу было выбрано число x, то в дальнейшем в игре нельзя выбирать само число x и все его остальные натуральные степени (x2, x3, ...). К примеру, если на первом ходу выбрано число 9, то в дальнейшем числа 9 и 81 выбирать нельзя, в то время как числа 3 и 27 выбрать разрешается. Проигрывает тот, кто не может сделать ход.
Кто выигрывает при оптимальной игре обоих соперников?
Единственная строка входных данных содержит натуральное число n (1 ≤ n ≤ 109).
Выведите имя победителя — «Vasya» или «Petya» (без кавычек).
1
Vasya
2
Petya
8
Petya
В первом примере Вася выберет 1 и сразу выиграет.
Во втором примере вне зависимости от первого хода Васи Петя сможет выбрать оставшееся число и победить.
Название |
---|