Задача MChess
Одного разу хлопець, що цікавиться олімпіадними задачами
з програмування, пішов на прогулянку до лісу. Ходячи
поміж деревами лісу, він зустрів Злого Мішку, лісового
звіра, що не любить, коли хтось заходить до його лісу.
Мішка хотів принести хлопчика в жертву, але дізнавшись,
що хлопчик розуміється в програмуванні, вирішив зіграти з
ним у гру "Лісові Шахи".
Гра має наступні правила: на дошці розміром 3хN у першому
рядку дошки знаходяться N чорних пішаків Злого Мішки, у
третьому рядку знаходяться N білих пішаків хлопчика,
відповідно другий рядок пустий.
Злий Мішка та хлопчик ходять по черзі, починає хлопчик.
На кожному кроці гравець обирає пішак, яким або робить
хід, або б'є ворожого пішака. Відповідно до правил пішаки
ходять на одну клітину вперед, тобто якщо пішак білий, то
він може піти з третього рядка на другий, а потім з
другого на перший. Якщо пішак чорний, то все навпаки, він
може піти з першого рядка на другий, а потім з другого на
третій. Звісно, та клітинка, на яку ходить пішак, має бути
пустою. Пішак б'є фігури по діагоналі на одну клітинку. В
грі "Лісові Шахи" бити фігури є обов'язковим, тобто якщо
можна бити фігуру, то її треба обов'язково побити на
цьому кроці! Програє той, хто не зможе зробити хід.
Ваша задача допомогти хлопчику вказати всі можливі перші
ходи, що 100% призведуть до його виграшу, якщо він буде
дотримуватись оптимальної стратеґії.
Технічні
умови. Програма читає з клавіатури
одне число N (1<=N<=1000).
Програма виводить на екран спочатку число
K, що є
кількістю перших ходів хлопчика, що 100% приведуть його
до виграшу, якщо він буде дотримуватись оптимальної
стратеґії. Якщо таких немає, тоді треба вивести
0. Далі
йдуть K чисел у порядку зростання, що показують, яким
за номером білим пішаком повинен піти хлопчик.
Білі пішаки нумеруються від 1 до N зліва направо.
Всі числа виводяться через пропуск.
Приклади.
Введення>
3
Виведення>
1 2
Введення>
2
Виведення>
2 1 2