Codeforces Beta Round 73 (Div. 1 Only) |
---|
Закончено |
Два лучших друга Сережа и Гена играют в игру.
Изначально на столе находится одна кучка из n камней. За один ход нужно взять одну кучку и разбить ее на произвольное число кучек размерами a1 > a2 > ... > ak > 0 камней так, что a1 - a2 = a2 - a3 = ... = ak - 1 - ak = 1. Естественно, количество кучек k должно быть не меньше двух.
Друзья делают ходы по очереди. Проигрывает тот, кто не может сделать ход. Начинает Сережа. Кто выиграет при оптимальной игре обоих?
В единственной строке записано одно целое число n (1 ≤ n ≤ 105).
Если выигрывает Сережа, выведите k — минимальное число кучек, на которое он может разбить исходную первым ходом при выигрышной стратегии.
Если выигрывает Гена, выведите «-1» (без кавычек).
3
2
6
-1
100
8
Название |
---|