Задача 4 регионального этапа Всероссийской олимпиады школьников по информатике 2011/2012 учебного года (offline)

Задачу добавил: alef

Успешно сдано решений: 3

Игра с числами

Входной файл:   input.txt
Выходной файл:  output.txt
Ограничение по времени:    2 секунды
Ограничение по памяти:    256 мегабайт

Сегодня на уроке математики Петя и Вася изучали понятие арифметической прогрессии. Арифметической прогрессией с разностью d называется последовательность чисел a₁, a₂, …, a_k, в которой разность между любыми двумя последовательными числами равна d. Например, последовательность 2, 5, 8, 11 является арифметической прогрессией с разностью 3.
После урока Петя и Вася придумали новую игру с числами. Игра проходит следующим образом.
В корзине находятся n фишек, на которых написаны различные целые числа a₁, a₂, …, a_n. По ходу игры игроки выкладывают фишки из корзины на стол. Петя и Вася делают ходы по очереди, первым ходит Петя. Ход состоит в том, что игрок берет одну фишку из корзины и выкладывает ее на стол. Игрок может сам решить, какую фишку взять. После этого он должен назвать целое число d ≥ 2 такое, что все числа на выбранных к данному моменту фишках являются членами некоторой арифметической прогрессии с разностью d, не обязательно последовательными. Например, если на столе выложены фишки с числами
2, 8 и 11, то можно назвать число 3, поскольку эти числа являются членами приведенной в начале условия арифметической прогрессии с разностью 3.
Игрок проигрывает, если он не может сделать ход из-за отсутствия фишек в корзине или из-за того, что добавление любой фишки из корзины на стол приводит к тому, что он не сможет подобрать соответствующее число d.
Например, если в корзине имеются числа 2, 3, 5 и 7, то Петя может выиграть. Для этого ему необходимо первым ходом выложить на стол число 3. После первого хода у него много вариантов назвать число d, например он может назвать d = 3. Теперь у Васи два варианта хода.
1)    Вася может вторым ходом выложить фишку с числом 5 и назвать d = 2. Тогда Петя выкладывает фишку с числом 7, называя d = 2. На столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2. Вася не может ее выложить, поскольку после этого он не сможет назвать корректное число d. В этом случае Вася проигрывает.
2)    Вася может вторым ходом выложить фишку с числом 7 и также назвать, например, d = 2. Тогда Петя выкладывает фишку с числом 5, называя также d = 2. Вася снова попадает в ситуацию, когда на столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2, и он также проигрывает.
Заметим, что любой другой первый ход Пети приводит к его проигрышу. Если он выкладывает число 2, то Вася отвечает числом 7, и Петя не может выложить ни одной фишки. Если Петя выкладывает фишку с числом 5 или 7, то Вася выкладывает фишку с числом 2, и у Пети также нет допустимого хода.
Требуется написать программу, которая по заданному количеству фишек n и числам на фишках a₁, a₂, …, a_n определяет, сможет ли Петя выиграть вне зависимости от действий Васи, и находит все возможные первые ходы Пети, ведущие к выигрышу.

Формат входного файла

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200).
Вторая строка содержит n различных целых чисел a₁, a₂, …, a_n  (для всех i от 1 до n выполняется неравенство 1 ≤ a_i ≤ 10⁵). Соседние числа разделены ровно одним пробелом.

Формат выходного файла

Первая строка выходного файла должна содержать число k — количество различных первых ходов, которые может сделать Петя, чтобы выиграть. Если Вася может выиграть вне зависимости от действий Пети, строка должна содержать цифру 0.
Во второй строке должно содержаться k различных целых чисел — все выигрышные числа. Будем называть число выигрышным, если, выложив в качестве первого хода фишку, содержащую это число, Петя может выиграть вне зависимости от действий Васи. Соседние числа в строке должны быть разделены ровно одним пробелом.

Пример входного файла - 1
4
2 3 5 7   

Пример выходного файла - 1
1
3

Пример входного файла - 2
2
2 4   

Пример выходного файла - 2
0


Пояснения к примерам
Первый пример рассматривается  в тексте условия этой задачи.
Во втором примере, какую бы фишку не выложил Петя первым ходом, Вася в ответ выкладывает другую фишку, и Петя не может сделать ход из-за отсутствия фишек в корзине.
Система оценивания
Правильные решения для тестов, в которых 1 ≤ n ≤ 15, будут оцениваться из 40 баллов.

Сдать задачу

Задать вопрос жюри по этой задаче