Задача №115181. Нужно больше тренироваться
Мальчик Антон учится в \(6\) классе и активно готовится к олимпиадам по программированию. На данный момент он уже сдал \(n\) задач, причем \(i\)-ю задачу он сдал в час \(t_i\).
Существует \(m\) часовых поясов, пронумерованных от \(0\) до \(m-1\). В каждом часовом поясе один день состоит из \(m\) последовательных часов. При том в \(k\)-м часовом поясе \(d\)-й день состоит из часов с номерами от \(d \cdot m + k\) до \((d + 1) \cdot m + k -1\) (включительно). Обратите внимание, что \(d\) может быть отрицательным.
В начале года Антон поставил себе цель сдавать как минимум по одной задаче каждый день. Сейчас он хочет проверить, существует ли такой часовой пояс и два дня \(l\) и \(r\), такие что в любой из этих дней он сдал хотя-бы одну задачу, а также любая сданная задача была сдана именно в один из дней от \(l\) до \(r\) в этом часовом поясе.
Помогите Антону найти такой часовой пояс, или определите, что его не существует. Если подходящих часовых поясов несколько — найдите минимальный из них.
Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \leq n \leq 200\,000\), \(1 \leq m \leq 10^9\)) — количество сданных задач и количество часов в каждом дне соответственно.
Вторая строка содержит \(n\) целых чисел \(t_1,\ t_2,\ t_3,\ \ldots,\ t_n\) (\(0 \leq t_i \leq 10^9\), \(t_i \le t_{i+1}\)) — время сдачи каждой задачи в неубывающем порядке.
Выведите одно целое число — минимальный номер подходящего часового пояся, или \(-1\), если его не существует.
В первом примере день идёт 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 посылки Антона попадают в дни 0, 0, 1, 3, 3 и 3 соответственно. Так как в день 2 Антон не сделал ни одной посылки, этот пояс не подходит.
- В часовом поясе 2 посылки Антона попадают в дни -1, 0, 1, 2, 3 и 3 соответственно. Дни образуют непрерывный отрезок от -1 до 3, поэтому этот пояс и является ответом.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(t_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 18 | \(n \le 500\) | \(m \le 100\) | – | \(0\) | |
| 2 | 19 | – | \(m \le 100\) | – | \(0\), \(1\) | |
| 3 | 16 | \(n \le 500\) | – | \(t_i \le 500\) | \(0\) | |
| 4 | 21 | \(n \le 5000\) | – | \(t_i \le 500\) | \(0\), \(3\) | |
| 5 | 26 | – | – | – | \(0\) – \(4\) | |
3 3 4 5 10
2
4 5 2 4 14 17
-1
6 3 1 2 6 10 11 12
2