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

Входной файл: in   Ограничение времени:1 сек
Выходной файл: out   Ограничение памяти:256 Мб
Максимальный балл:50  

Условие

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

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

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

В единственной строке содержатся два натуральных числа, разделенных пробелом: N – количество обезьянок и K – количество свободных вольеров (1 ≤ K ≤ N ≤ 109).

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

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

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

Входной файл (in) Выходной файл (out)
1
7 4
2 4
2
12 3
4 10

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

Входной файл: in   Ограничение времени:1 сек
Выходной файл: out   Ограничение памяти:256 Мб
Максимальный балл:50  

Условие

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

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

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

В первых трех строках записаны три целых числа A, B, С, — размеры окладов Василия, Алексея и Сергея (A > 0, B > 0, С > 0). В четвёртой строке входных данных записано одно целое число N — размер премиального фонда (N ≥ 0).

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

Программа должна вывести три числа — размер премии Василия, Алексея и Сергея. Если премиальный фонд нельзя распределить так, чтобы выполнялись требуемые условия, программа должна вывести одно число 0.

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

Входной файл (in) Выходной файл (out)
1
7
3
4
12
5
3
2
2
20
10
11
2
0

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

Входной файл: in   Ограничение времени:2 сек
Выходной файл: out   Ограничение памяти:256 Мб
Максимальный балл:70  

Условие

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

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

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

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

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

В первой строке входного файла даны два натуральных числа m и n — число досок в заборе и число дней, в течение которых вел свои наблюдения Петр (1 ≤ m ≤ 10000, 1 ≤ n ≤ 1000). Далее, в n строках заданы целые числа li, ri(1 ≤ li ≤ ri ≤ m), i-я пара чисел описывает отрезок забора, который покрывался граффити в i-й день.

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

Выведите «YES», если весь забор был заклеен объявлениями, и «NO» в противном случае.

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

Входной файл (in) Выходной файл (out)
1
3 3
1 1
2 2
3 3
YES

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

Входной файл: in   Ограничение времени:1 сек
Выходной файл: out   Ограничение памяти:256 Мб
Максимальный балл:80  

Условие

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

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

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

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

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

В первой строке содержатся два натуральных числа A и B – размеры кухни (1 ≤ A, B < 105). Во второй строке содержатся два целых числа x и y – размеры одной плитки (1 ≤ x < A, 1 ≤ y < B).

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

Выведите одно число – минимальное число плиток, которое необходимо купить Ане и Васе. Помните, плитки ни в коем случае нельзя поворачивать!

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

Входной файл (in) Выходной файл (out)
1
10 10
2 2
25
2
3 5
2 2
4
3
35 17
25 1
26

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

Входной файл: in   Ограничение времени:3 сек
Выходной файл: out   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

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

В первой строке содержатся натуральное число N – общее количество продовольственных товаров на рынке (1 ≤ N ≤ 500). В следующих N строках содержатся описания товаров, каждый товар описывается тремя натуральными числами ci – стоимость товара, ai – время завоза, bi – время вывоза (1 ≤ ci ≤ 1000, 1 ≤ ai < bi ≤ 109). В следующей строке содержится число M – количество планов Ани и Васи (1 ≤ M ≤ 500000). В следующих M строках описаны планы. Каждый план описывается тремя числами mj – время прихода Ани и Васи, kj – сумма денег, sj – время пребывания (1 ≤ mj ≤ 109, 1 ≤ kj ≤ 100000, 0 ≤ sj ≤ 109).

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

Для каждого плана в отдельной строке вывести «YES», если Анна и Вася смогут его осуществить, и «NO» в обратном случае.

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

Входной файл (in) Выходной файл (out)
1
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

0.049s 0.006s 15