Олимпиадный тренинг

Задача . Fair Photography

Задача

N (1 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова находится на позиции x_i (целое число в интервале 0...1,000,000,000) и имеет породу b_i (целое число в интервале 1..8). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фотографию непрерывного интервала коров, но так чтобы все породы коровы были представлены одинаковым количеством коров. Например, фото из 27 коров породы 1 и 27 коров породы 3 – подходит, фото из 27 коров породы 1 и 27 коров породы 3 – подходит и 27 коров породы 4 тоже подходит, а 9 породы 1 и 10 породы 3 не подходит. ФД также хочет чтобs по крайнеq мере K (K>=2) пород из 8 имеющихся были представлены на фото. Помогите ФД определить фот максимального размера, которое удовлетворяет требованиям ФД. Размер фото – это разница между максимальной и минимальной позициями коров на фото.
Если не существует фото, удовлетворяющего всем ограничениям, выведите -1.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: N и K разделённые одним пробелом
* Строки 2..N+1: Каждая строка содержит описание одной коровы двумя целыми числами, разделёнными одним пробелом: x_i и ID-породы

Примечание
ID пород: 1 2 3 - 1 1 2 3 1 - ... - 1 Местоположения: 1 2 3 4 5 6 7 8 9 10 ... 99 100
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальный размер подходящего фото. Если таких фото нет, выведите -1.

Примечание
В интервале от x = 2 до x = 8 имеется по 2 коровы каждой из пород 1, 2,3. В интервале от 9 до 100 есть 2 коровы породы 1, но поскольку K=2, этот интервал не подходит.

Примеры

№	Входные данные	Выходные данные
1	9 2 1 1 5 1 6 1 9 1 100 1 2 2 7 2 3 3 8 3	6

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

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

Загруженные файлы

Нет