ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Квадратная страна 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Квадратная Дума Квадратной страны постановила создать Национальный квадратный парк. Конечно же, парк должен занимать большой квадрат. К сожалению, на данный момент многие квадратные граждане инвестировали (не без помощи участников последнего чемпионата) свои квадрики в землю так, что часть страны уже занята. Возможно, не получится найти землю для парка, не затрагивая интересы частных владельцев. Если это действительно так, некоторые участки земли придется экспроприировать.
Во избежание социальных волнений Дума должна разместить парк так, чтобы были затронуты интересы как можно менее влиятельных граждан. Лучше экспроприировать землю у тысячи простых граждан, чем у одного депутата или одного владельца банка.
Все земли, принадлежащие жителям Квадратной страны, отмечены целыми числами от 2 до 100 в зависимости от влиятельности владельца: земли Квадратного президента отмечены числом 100, земли олигархов – числом 99, земли депутатов – числом 98 и т.д.
Кроме того, некоторые земельные участки принадлежат членам (не квадратного) жюри, которые придумали эту задачу. Эта земля отмечена числом 255 и не может быть экспроприирована вообще.

Исходные данные

В первой строке указаны целые числа L и A – длина стороны Квадратной страны и длина стороны парка соответственно (1 ≤ AL ≤ 10000). Следующая строка содержит целое число M – количество занятых участков земли (1 ≤ M ≤ 100). Согласно квадратным законам, участок земли – это квадрат с целыми координатами вершин, стороны которого параллельны осям координат. Координаты левого нижнего угла Квадратной страны – (1, 1).
Следующие M строк содержат информацию о занятых участках земли: влиятельность владельца, длину стороны квадрата и координаты левого нижнего угла. Влиятельность – целое число от 2 до 100 или число 255. Длина и координаты – целые числа от 1 до L. Каждый участок земли целиком находится в пределах страны и может пересекаться с другими участками земли только по своей границе. Вся земля, не принадлежащая ни одному занятому участку, является свободной.

Результат

Если можно построить парк на свободных землях, выведите число 1. Иначе выведите минимально возможную влиятельность владельцев земли, которую нужно экспроприировать (целое число от 2 до 100). Количество и площадь экспроприированных земельных участков не имеют значения. Следует учитывать влиятельность только самых влиятельных землевладельцев среди тех, которые пострадают от создания парка.
Если невозможно создать парк, не включающий в себя земли членов жюри, выведите слово «IMPOSSIBLE».

Примеры

исходные данныерезультат
5 3
6
94 2 4 1
3 1 1 1
2 1 1 2
2 2 2 1
100 1 2 4
255 1 5 5
3
5 3
1
255 1 3 3
IMPOSSIBLE

Замечания

Problem illustration
На рисунке изображен первый пример. Парк можно создать на участке, отмеченном серым цветом. Чтобы сделать это, потребуется экспроприировать участки, принадлежащие собственникам с влиятельностью 2 и 3.
Автор задачи: Станислав Васильев
Источник задачи: USU Open Collegiate Programming Contest March'2001 Senior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1097. Квадратная страна 2