Задача №112813. Беги, Форрест, беги! (З)
Юный спортсмен Гамп собирается пробежать по дорожке, состоящей из клеток.
Бег происходит следующим образом: изначально Гамп занимает ногой на дорожке только клетки - A + 1, ..., 0, где A — длина стопы Гампа.
\)A = 2\(; до начала бега
Затем он делает шаг и занимает ногой только клетки B, ..., B - A + 1, где B — длина шага Гампа. После следующего шага он занимает только клетки 2B, ..., 2B - A + 1 и так далее. Другими словами, каждый раз занимаемая область сдвигается на B клеток вправо.
\)A = 2\(, \)B = 3\(; после первого шага
\)A = 2\(, \)B = 3\(; после второго шага
Непосредственно перед забегом выяснилось, что некоторые клетки дорожки были только что покрашены. Гамп не хочет отстирывать свои любимые кроссовки, поэтому он решил отступить на несколько клеток назад перед тем, как начать забег.
Гамп может отступить на любое количество клеток строго меньшее B (а может и вовсе не отступать), после чего начать забег по описанным выше правилам.
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; до начала бега
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; после первого шага
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; после второго шага
Помогите Гампу выбрать отступ, начав с которого он наступит на минимальное количество покрашенных клеток.
В первой строке содержатся два целых числа A и B — длины стопы и шага Гампа соответственно (1 ≤ A ≤ B ≤ 200 000).
Во второй строке содержится единственное целое число N — количество покрашенных клеток (1 ≤ N ≤ 200 000).
В третьей строке содержатся N целых чисел — номера покрашенных клеток в возрастающем порядке. Все номера не меньше 1 и не превосходят 109.
Выведите два числа — на сколько клеток нужно отступить Гампу, чтобы наступить на минимально возможное количество покрашенных клеток, и это количество соответственно.
Если правильных ответов несколько, выведите любой из них.
2 3
2
2 5
2 0
1 5
9
1 2 3 4 5 6 7 8 9
0 1
В первом примере возможны следующие варианты:
\)A = 2\(, \)B = 3\(; отступ — 0; наступил на две покрашенные
\)A = 2\(, \)B = 3\(; отступ — 1; наступил на две покрашенные
\)A = 2\(, \)B = 3\(; отступ — 2; не наступил на покрашенные
Во втором примере отступать не нужно:
\)A = 1\(, \)B = 5$; отступ — 0; наступил на одну покрашенную
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. B, N ≤ 100. Номера покрашенных клеток не превосходят 100. Оценивается из 20 баллов.
Подзадача 2. B, N ≤ 1000. Оценивается из 20 баллов.
Подзадача 3. B, N ≤ 200 000. Номера покрашенных клеток не превосходят 200 000. Оценивается из 30 баллов.
Подзадача 4. B, N ≤ 200 000. Оценивается из 30 баллов.