11/04/2025 02:07:15

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2826. Круговая порука

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Все сотрудники департамента, в котором работает Дмитрий, делятся на честных и коррумпированных, причем все знают друг про друга, кто кем является. В департамент прибыла проверка, всех сотрудников усадили за круглый стол и задали каждому один и тот же вопрос: сколько коррумпированных среди следующих $K$ сотрудников справа от вас? Все честные сотрудники отвечали верно. А коррупционеры стремились запутать проверяющих и всегда давали ответ, отличающийся от истинного ровно на 1. То есть, если справа $X$ коррупционеров, то коррумпированный сотрудник назовет число $X+1$ или $X-1$ (но не меньше 0: если справа все сотрудники честные, то единственный возможный ответ - это 1). Помогите по результатам опроса установить минимальное и максимальное возможное количество коррупционеров в департаменте.

В первой строке ввода содержатся 2 целых числа: количество сотрудников в департаменте $N$ ( $2 <= N <= 1000$ ) и число из опроса $K$ ( $1 <= K <= min(N-1,10)$ ). Во второй строке ввода содержатся $N$ целых чисел $a_i$ – ответы, названные сотрудниками ( $0 <= a_i <= K+1$ ).

В единственной строке выведите два неотрицательных целых числа, не превосходящих $N$ : минимальное и максимальное возможное количество коррупционеров, не противоречащее результатам опроса. Гарантируется, что для каждого теста существует хотя бы одна подходящая рассадка.

Пример ввода 1

4 1
0 0 0 0

Пример вывода 1

0 4

Пример ввода 2

5 1
1 1 1 1 0

Пример вывода 2

2 3

Система оценки и описание подзадач

Подзадача 1 (20 баллов)

$K=1$ , остальные ограничения из условий задачи.

Подзадача 2 (30 баллов)

$2<=N<=10$ , остальные ограничения из условий задачи.

Подзадача 3 (50 баллов)

Ограничения из условий задачи

Необходимые подзадачи: 1, 2.

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.