Открытая олимпиада по программированию 2023-2024 Отбор Длинный тур Задача А

Моя анкета на профи ру Ассоциация репетиторов Мой вк Группа вк Ссылка на дорешивание задач Сайт олимпиады Задача A. Нужно больше тренироваться Имя входного файла: стандартный ввод или Имя выходного файла: стандартный вывод или Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Мальчик Антон учится в 6 классе и активно готовится к олимпиадам по программированию. На данный момент он уже сдал n задач, причем i-ю задачу он сдал в час ti . Существует m часовых поясов, пронумерованных от 0 до m − 1. В каждом часовом поясе один день состоит из m последовательных часов. При том в k-м часовом поясе d-й день состоит из часов с номерами от d · m k до (d 1)· m k − 1 (включительно). Обратите внимание, что d может быть отрицательным. В начале года Антон поставил себе цель сдавать как минимум по одной задаче каждый день. Сейчас он хочет проверить, существует ли такой часовой пояс и два дня l и r, такие что в любой из этих дней он сдал хотя-бы одну задачу, а также любая сданная задача была сдана именно в один из дней от l до r в этом часовом поясе. Помогите Антону найти такой часовой пояс, или определите, что его не существует. Если подходящих часовых поясов несколько — найдите минимальный из них. Формат входных данных Первая строка содержит два целых числа n и m (1 6 n 6 200 000, 1 6 m 6 109 ) — количество сданных задач и количество часов в каждом дне соответственно. Вторая строка содержит n целых чисел t1, t2, t3, . . . , tn (0 6 ti 6 109 , ti 6 ti 1) — время сдачи каждой задачи в неубывающем порядке. Формат выходных данных Выведите одно целое число — минимальный номер подходящего часового пояся, или −1, если его не существует. Примеры стандартный ввод стандартный вывод 3 3 4 5 10 2 4 5 2 4 14 17 -1 6 3 1 2 6 10 11 12 2 Замечание В первом примере день идёт 3 часа и Антон сдал 3 задачи: в часы 4, 5 и 10 соответственно. • В часовом поясе 0 посылки Антона попадают в дни 1, 1 и 3 соответственно. Так как в день 2 Антон не сделал ни одной посылки, этот пояс не подходит. • В часовом поясе 1 посылки Антона попадают в дни 1, 1 и 3 соответственно. Так как в день 2 Антон не сделал ни одной посылки, этот пояс не подходит. • В часовом поясе 2 посылки Антона попадают в дни 0, 1 и 2 соответственно. Дни образуют непрерывный отрезок, а значит этот пояс подходит. Так как он минимальный среди подходящих, 2 является ответом на задачу. Во втором примере ни один из часовых поясов не подходит. В третьем примере: • В часовом поясе 0 посылки Антона попадают в дни 0, 0, 2, 3, 3 и 4 соответственно. Так как в день 1 Антон не сделал ни одной посылки, этот пояс не подходит. Страница 1 из 23 Длинный тур отборочного этапа Открытой олимпиады школьников 2023–2024 учебного года 25 Ноября 2023 – 15 января 2024 • В часовом поясе 1 посылки Антона попадают в дни 0, 0, 1, 3, 3 и 3 соответственно. Так как в день 2 Антон не сделал ни одной посылки, этот пояс не подходит. • В часовом поясе 2 посылки Антона попадают в дни -1, 0, 1, 2, 3 и 3 соответственно. Дни образуют непрерывный отрезок от -1 до 3, поэтому этот пояс и является ответом.