Задача B. Арифметическая прогрессия

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

Условие

Петя очень любит арифметические прогрессии. Однажды он написал на бумаге числовую последовательность, но, к сожалению, эта последовательность не оказалась арифметической прогрессией.

Чтобы исправить эту ситуацию, Петя решил вычеркнуть некоторые числа, чтобы полученная в результате вычёркивания последовательность оказалась арифметической прогрессией. При этом Петя хочет вычеркнуть как можно меньше чисел.

Напишите программу, принимающую на вход последовательность чисел и вычисляющую, какое наименьшее количество чисел нужно из неё вычеркнуть, чтобы оставшаяся последовательность оказалась арифметической прогрессией.

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

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел ai.

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

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1 3 4 2 7 8 10
4
1 3 5 7

Разбор

Для решения задачи применим перебор плюс жадный алгоритм.

Требуется найти в данной последовательности чисел арифметическую прогрессию p1, p2, ..., pM наибольшей длины. По определению арифметической прогрессии, pi + 1 − pi = d = const. Справедлива следующая формула для i-го члена прогрессии: pi = p1 + (i − 1)d. Таким образом, если известны p1 и d, то арифметическая прогрессия определена однозначно.

Поскольку в задаче заранее неизвестно, какую конкретно арифметическую прогрессию нужно найти, напрашивается перебрать параметры p1 и d. Для перебора p1 будем перебирать индекс i первого члена прогрессии (ai = p1). Чтобы перебрать d, будем перебирать индекс j (j > i) второго члена прогрессии (aj = p2). Тогда d = p2 − p1 = aj − ai.

Теперь, когда мы перебрали i и j, нам известно, какую арифметическую прогрессию p1, p2, ..., pM нужно искать в исходной последовательности. Местонахождения первого p1 и второго p2 членов прогрессии уже известны. Чтобы найти p3, применим последовательный поиск среди чисел aj + 1, aj + 2, ..., aM. Возможно два случая.

  1. Среди этих чисел нет элемента, равного p3. В этом случае прогрессии длины 3 с данными параметрами p1 и d в исходной последовательности нет.
  2. Среди этих чисел есть элемент, равный p3.
    • Такой элемент ровно один. В этом случае местонахождение p3 определено однозначно.
    • Таких элементов несколько. В этом случае нужно взять элемент с меньшим индексом (применяем жадный алгоритм).

Аналогичным образом ищем p4, p5 и т.д.


0.061s 0.008s 13