При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

• входные данные в формате, описанном в условии предыдущей задачи,
• ответ некоторого абстрактного участника в формате, также описанном в предыдущем условии,
• ответ жюри.

Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.

Прямоугольная детская площадка полностью замощена \(N\) плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.

На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.

Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c _i , время его завоза в магазин a _i и время его вывоза из магазина b _i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m _j , время s _j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k _j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k _j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.

Королевские Железные Дороги (КЖД) готовятся открыть новый, скоростной, маршрут из столицы в соседний город NN и обратно. Новые поезда будут добираться до места назначения втрое быстрее обычных ночных поездов. Конкурс на поставку новых составов выиграла зарубежная компания «MacroHard» — производитель локомотивов «Hawk», которые будут использоваться в королевстве под локализованным названием «Ястреб». Расписание уже готово, но до сих пор не решен вопрос, сколько именно составов нужно, чтобы его выполнить. Не требуется покупать по составу на каждый рейс, поскольку поезд, прибывший на станцию, может выполнить и обратный рейс. КЖД обратились к вам и просят написать программу, способную рассчитать минимально необходимое количество поездов на один день. Расписание состоит из N ₁ рейсов из столицы в город NN и N ₂ обратных рейсов. Для каждого рейса известно время отправления и время прибытия — с точностью до минуты. Любой рейс полностью выполняется в течение одних календарных суток (с 00: 00 до 23: 59 включительно) — то есть никакой рейс не прибывает на следующий день после отправления. Каждый рейс занимает как минимум одну минуту, то есть ни один поезд не прибывает на станцию назначения в ту же минуту, в которую он отправился . КЖД настолько эффективны, что после прибытия поезд готов в ту же минуту отправиться в обратный рейс. Одновременно на станции может находиться, отправляться или прибывать любое количество поездов. Руководство КЖД не одобряет холостые поездки, поэтому поезда не могут перемещаться вне расписания в течение дня. Отметим, что вам не нужно учитывать подготовку к выполнению расписания следующего дня — к моменту начала следующих суток железнодорожники способны обеспечить любое распределение составов по станциям, независимо от того, как они были распределены к концу предыдущих.