Задача 1. Обезьянки ≡

Условие

На днях в Елизовский зоопарк прибыли новые жильцы – N обезьянок. Администрации зоопарка предстоит решить, как лучше всего распределить N обезьянок по имеющимся в зоопарке K свободным вольерам таким образом, чтобы ни один вольер не остался пустым. Главным критерием при размещении является комфортное обитание обезьян, поэтому администрацию в первую очередь интересует, сколько обезьянок окажется в самом заполненном вольере (то есть в вольере с максимальным числом обезьянок).

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

Формат входного файла

Формат выходного файла

Примеры тестов

7 4

2 4

12 3

4 10

Задача 2. Премии ≡

Условие

В некоторой IT компании работают три программиста — недавно женившийся Василий, Алексей и Сергей. Их месячный оклад составляет B, A и C рублей соответственно.

За отличную работу по итогам месяца директор компании хочет выплатить сотрудникам премии. Премиальный фонд составляет N рублей. При этом щедрый директор хочет сделать Василию подарок на свадьбу и распределить премиальный фонд таким образом, чтобы итоговая зарплата (сумма оклада и премии) у Василия оказалась ровно в два раза больше, чем итоговая зарплата Алексея и Сергея. При этом бухгалтерия требует, чтобы размер премии (как и размер оклада) выражался целым числом рублей, а директор хочет распределить максимально большую часть премиального фонда, то есть сумма x + y + z должна быть максимально возможной, не превышая при этом N. Напишите программу, которая определит, какую премию нужно назначить каждому из сотрудников.

Формат входного файла

Формат выходного файла

Примеры тестов

7
3
4
12

5
3
2

20
10
11
2

0

Задача 3. Граффити ≡

Условие

Устав от городской суеты, молодожены Аня и Вася купили небольшой и симпатичный домик в деревне. Вдоль их участка расположен красивый деревянный забор. Но недавно в деревне поселился граффитист, разрисовывающий чужие заборы. И забор Ани и Васи не стал исключением.

Каждый день на заборе появляется новый рисунок. Таким образом за последние n дней на забор нанесено уже n изображений и молодоженам кажется, что испорчен уже весь забор, состоящий из m досок. Доски пронумерованы вдоль забора от 1 до m.

Оказалось, что в каждый из n дней, когда приходил граффитист и рисовал граффити, неравнодушный сосед Петр записывал, какие доски оказывались изрисованы. А именно, выяснилось что в i-й день очередной рисунок был нанесен таким образом, что занимал доски с l_i-й по r_i-ю включительно. При этом граффитист вполне мог зарисовать полностью или частично свое же собственное творение.

Для составления жалобы в администрацию деревни Ане и Васе необходимо удостовериться, что испорчен весь забор. Помогите им выяснить, так ли это.

Формат входного файла

Формат выходного файла

Примеры тестов

3 3
1 1
2 2
3 3

YES

Задача 4. Кафельная плитка ≡

Условие

Молодожены Аня и Вася решили устроить ремонт на кухне. На семейном собрании было решено, что лучшим половым покрытием для кухни является плитка.

Кухня Ани и Васи представляет собой прямоугольник со сторонами A на B метров. Посетив строительный магазин, Аня и Вася выбрали плитку с интересным узором. Каждая плитка имеет фиксированный размер x на y метров. Для того чтобы пол выглядел аккуратно и красиво, плитку надо класть так, чтобы каждая сторона плитки граничила максимум с одной плиткой и была параллельна одной из сторон кухни. Выбранный узор оказался очень специфическим, поэтому плитки нельзя поворачивать, даже все одновременно – сторона кухни длиной A должна быть всегда параллельна стороне плитки длиной x.

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

Аня и Вася хотят сэкономить семейный бюджет и замостить кухню так, чтобы было использовано минимально возможное количество плиток и их частей. Помогите молодоженам выяснить, какое количество плиток размером x на y нужно приобрести, чтобы замостить кухню.

Формат входного файла

Формат выходного файла

Примеры тестов

10 10
2 2

25

3 5
2 2

4

35 17
25 1

26

Задача 5. Рынок ≡

Условие

На центральном рынке часто происходит распродажа различных продовольственных товаров. Каждый товар привозят на рынок в определенное время, и через некоторое время увозят, то есть каждый товар имеет стоимость c_i, время завоза a_i и время вывоза b_i.

Молодожены Аня и Вася запланировали несколько походов на рынок на следующий месяц. План похода выглядит следующим образом: Аня и Вася выбирают время m_j, когда они появятся на рынке, сумму денег k_j, которую они планируют потратить и время s_j, которое они проведут на рынке. Аня и Вася хотят узнать, смогут ли они осуществить свои планы, то есть верно ли, что они смогут во время своего пребывания на рынке накупить товаров суммарной стоимостью ровно k_j, при этом все выбранные товары должны быть на рынке на протяжении всего пребывания Ани и Васи.

Формат входного файла

Формат выходного файла

Примеры тестов

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

YES
NO
YES
YES
NO