Разбор добавил Анатолий Варивончик

пусть (F[i] = 1) если выигрывает первый и (F[i] = 2) если второй. Тогда заметим, что F[1]=1,F[2]=1 F[3] = 2. Теперь мы просто заполним наш массив F. Будем считать, что 1 это выигрышная позиция 2 проигрышная. Тогда если мы можем из теперешней позиции попасть в проигрышную, то она выигрышная, а если мы попадаем только в выигрышные, то наша позиция проигрышная. Осталось пробежаться циклом от 4 до n. И выписать условия для разной кратности 3. На самом деле, потом можно заметить, что позиции кратные 3ём проигрышные, а все остальные выигрышные.