ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: Second Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Pascal против C++

Ограничение времени: 0.25 секунды
Ограничение памяти: 16 МБ

Вступление

Знаете, нам абсолютно не важно, кто и на каком языке пишет. Мы давно вышли из этих игр. Basic, Pascal, C++ или Java - пусть каждый выбирает сам. Просто не надо лишать нас этого выбора. Мы выражаем свой протест организаторам ACM ICPC, исключившим Pascal из списка языков программирования чемпионата, и посвящаем им эту задачу.
Программист Андрей Забодяжный с наслаждением глотнул кваса и откинулся на спинку табуретки. Спинка у табуретки, разумеется, отсутствовала, и поэтому не было ничего удивительного в том, что секундой позже Андрей, отчаянно матерясь, летел на пол в сопровождении бутылки и табуретки. Но даже такое прискорбное событие - столько кваса зря пропало! - не могло испортить настроение прославленному программисту. Ведь он только что закончил последнюю версию программы, которая должна раз и навсегда доказать, что C++ - лучший язык программирования, а Intel C++ Compiler - самый быстрый компилятор современности. "Наконец-то задача решена... Мой алгоритм за O(N^5) - абсолютный оптимум... Pascal must die...", - такие мысли проносились в голове г-на Забодяжного, в то время как он сам лицезрел сквозь мутное стекло панораму родной Тмутаракани и потягивал остатки кваса...
В это же самое время в далёкой Мексике программист Педро Гомес, довольно ухмыляясь, восседал на мансарде собственной хибары и опрокидывал в себя очередную бутылочку мате. Буквально несколько минут назад дон Педро закончил программу всей своей жизни, которой было суждено установить тотальное доминирование легендарного языка программирования Pascal и самого лучшего компилятора в мире AMD Pascal Compiler - отныне и до конца времён! "Наш час настал... O(N^5) - быстрее некуда... C++ must die...", - могучий мозг г-на Гомеса был переполнен мудрыми мыслями...
Вам уже, наверное, интересно, что за задачу решали Андрей и Педро, и почему они оба свалились по тайм-лимиту уже на шестом тесте?

Задача

Последовательность S состоит из N элементов S[i], пронумерованных от 1 до N. Из этой последовательности необходимо выбрать максимальное количество различных элементов, являющихся последовательными членами некоторой возрастающей арифметической прогрессии. Порядок этих элементов в последовательности S не имеет значения. И да пребудет с Вами Pascal. Или C++?

Исходные данные

Первая строка содержит целое число N (2 ≤ N ≤ 2000). Вторая строка содержит N целых чисел S[i] (0 ≤ S[i] ≤ 109).

Результат

В первую строку вывести максимальное количество элементов. Во вторую строку вывести через пробел и в любом порядке номера этих элементов в последовательности S. Если задача имеет несколько решений, то вывести любое из них.

Пример

исходные данныерезультат
6
7 3 2 3 5 9
4
4 5 1 6

Замечания

Чтобы преодолеть тайм-лимит, Ваше решение должно быть по-настоящему быстрым.
Если Ваше решение работает быстрее 0.1 сек. и потребляет менее 1 Мб. памяти, то мы рекомендуем Вам обратить внимание на задачу "Pascal против C++. Версия 2".
Автор задачи: Илья Гребнов, Дмитрий Ковалёв, Никита Рыбак
Источник задачи: Timus Top Coders: Second Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1452. Pascal против C++