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

Открытое личное первенство УрФУ 2014

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

H. Чем выше горы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Катя регулярно выезжает со своими друзьями на ближайший горнолыжный курорт — гору Шпильную — покататься на сноуборде. Только что там открыли новую трассу. Но когда Катя впервые прокатилась по этой трассе, её посетило ощущение дежавю, как будто она до этого уже каталась по точно такому же склону. Ну, или, может быть, чуть более крутому или пологому. Это настолько её взволновало, что вместо того, чтобы продолжить кататься, она решила проверить, не было ли на каком-то из склонов, по которым она каталась раньше, участка, который был бы похож на склон, по которому она только что съехала. Вернувшись в свою машину и достав ноутбук, Катя нашла в интернете подробную информацию о всех склонах, по которым она ездила, включая новый склон горы Шпильной, — карту высот с шагом в один метр. Катя считает похожими два участка разных склонов одинаковой длины, если для высот первого участка x0, x1, …, xn, высот второго участка y0, y1, …, yn и некоторых чисел a и b выполняется равенство xiyi = a · i + b.

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

В первой строке дано целое число n — количество склонов, по которым Катя каталась раньше (1 ≤ n ≤ 105). Во второй строке через пробел даны целое число m и целые числа x0xm, где m — длина склона, по которому Катя проехала только что, a xi — высота над уровнем моря точки, находящейся в i метрах от начала склона (1 ≤ m ≤ 105; −109xi ≤ 109). В следующих n строках в таком же формате описаны все склоны, по которым Катя каталась раньше. Гарантируется, что сумма их длин не превосходит 105.

Результат

Если существуют такие числа i и j, что склон, по которому только что проехала Катя, похож на участок, начинающийся с j-го метра от начала i-го склона из тех, по которым она ездила ранее, то выведите числа i и j через пробел. Склоны нумеруются целыми числами от 1 до n в том порядке, в котором они перечислены во входных данных. Если есть несколько подходящих пар i и j, выведите ту из них, при которой значение модуля параметра a из критерия похожести минимально. Если таких всё ещё несколько, выведите любую из них. Если таких чисел не существует, выведите −1.

Примеры

исходные данныерезультат
2
2 3 2 1
5 21 15 10 6 3 2
4 10 7 5 3 2
2 1
3
2 0 0 0
1 0 0
2 1 2 4
1 5 17
-1
Автор задачи: Дмитрий Иванков
Источник задачи: Открытое личное первенство УрФУ по программированию 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2097. Чем выше горы