Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Прыгающий робот

(Время: 3 сек. Память: 512 Мб Сложность: 37%)

Компания «Flatland Dynamics» разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из n специальных платформ, пронумерованных от 1 до n. Расстояние между i-й и i+1-й платформой равно di, аналогично расстояние между n-й и 1-й платформой равно dn.

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i+1, если a ≥ di. Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ≥ dn. При этом после каждого прыжка ловкость робота увеличивается на 1.

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

Входные данные

На первой строке входного файла INPUT.TXT находится число n (3 ≤ n ≤ 107).

Вторая строка содержит одно целое число f, которое описывает формат, в котором задан массив расстояний между платформами.

Если f = 1, то на третьей строке находятся n целых чисел d1, d2, ... , dn (1 ≤ di ≤ 109).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 105)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 109). На четвертой строке находятся m целых чисел c1, c2, ... , cm (1 ≤ ci ≤ 109). Значения di вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то di = ci.

Если m + 1 ≤ i ≤ n, то di = ((x · di−2 + y · di−1 + z) mod 109) + 1.

Здесь mod означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом «%».

Выходные данные

В выходной файл OUTPUT.TXT выведите два целых числа: минимальную допустимую начальную ловкость a и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

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

Примеры

INPUT.TXTOUTPUT.TXT
15
1
3 7 4 2 5
4 3
210
2
5 1 2 3
1 2 3 4 5
653 1

Пояснение

Во втором примере массив расстояний между платформами равен [1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d6 до d10 вычисляются по формулам:

d6 = ((1 · d4 + 2 · d5 + 3) mod 109) + 1 = ((1 · 4 + 2 · 5 + 3) mod 109) + 1 = 18

d7 = ((1 · d5 + 2 · d6 + 3) mod 109) + 1 = ((1 · 5 + 2 · 18 + 3) mod 109) + 1 = 45

d8 = ((1 · d6 + 2 · d7 + 3) mod 109) + 1 = ((1 · 18 + 2 · 45 + 3) mod 109) + 1 = 112

d9 = ((1 · d7 + 2 · d8 + 3) mod 109) + 1 = ((1 · 45 + 2 · 112 + 3) mod 109) + 1 = 273

d10 = ((1 · d8 + 2 · d9 + 3) mod 109) + 1 = ((1 · 112 + 2 · 273 + 3) mod 109) + 1 = 662


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Чемпионат по устному счету
 B. Прыгающий робот
 C. Треугольная головоломка
 D. Массивы-палиндромы
 E. Новый год в детском саду
 F. Сортировка дробей
 G. Оптические каналы связи
 H. Подарки

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru