Два двоечника, Петя и Вася, по дороге в школу хвастаются друг перед другом своими отметками. Петя утверждает, что по математике он уже получил не менее a двоек. Вася точно помнит, что его товарищ получил не более b двоек по этому предмету. Встретившийся им по пути учитель не помнил все отметки Пети, но точно знал, что у него в журнале ровно n отметок, которые в сумме дают s.
Попробуйте по этим данным определить наименьшее и наибольшее возможное количество двоек по математике в журнале у Пети. Считайте, что в журнал ставятся только следующие отметки: 2, 3, 4 и 5.
Формат входных данных
Первая строка входного файла содержит четыре натуральных числа, записанных через пробел: a, b, n и s. Гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите через пробел два неотрицательных целых числа — наименьшее и наибольшее возможное количество полученных Петей двоек.
На координатной плоскости две параболы заданы так, что линии их графиков образуют замкнутую область. У одной параболы ветви направлены вверх, а у другой вниз. Для заданной точки определите, попадает ли она в замкнутую область.
Формат входных данных
Первая строка входного файла содержит три целых числа, записанных через пробел: a1, b1 и c1 — коэффициенты первой квадратичной функции. Во второй строке в том же формате содержатся ещё три целых числа: a2, b2 и c2 — коэффициенты второй квадратичной функции. В третьей строке через пробел расположены два целых числа x и y — координаты точки. Гарантируется, что параболы, являющиеся графиками данных функций образуют на плоскости непустую замкнутую область.
Формат выходных данных
Выведите "Yes" или "No" (без кавычек) — ответ на поставленный вопрос. Если точка попадает на границу области, выведите "Yes".
Фил Коннорс проснулся утром во вторник, второго февраля. Опять. Он уже сам сбился со счета, сколько раз его будила навязчивая песня «I Got You Babe», раздающаяся из радио-будильника. Но в последнее время она уже не раздражала Фила, в его жизни настал период спокойствия и умиротворения. "Чем бы мне заполнить сегодняшний день?" — подумал он. Вариантов много. Можно почитать Чехова в библиотеке, взять урок музыки, поймать падающего мальчишку, заменить сломавшееся колесо или принести коллегам горячий кофе.
Второго февраля в городке Панксатони происходит много событий. Они характеризуются двумя параметрами: временем начала и продолжительностью. Естественно, что многие события происходят одновременно или частично накладываются по времени друг на друга, поэтому Фил не сможет принять участие во всех сразу. Помогите ему определить наибольшее количество событий, в которых он сможет принять участие. Фил не может завершить участие в событии, пока оно не закончится. Фил может принять участие в событии, которое начинается в то же время, в которое заканчивается предыдущее событие, в котором Фил участвует.
Формат входных данных
Первая строка входного файла содержит натуральное число n — общее количество событий. В следующих n строках через пробел расположены два целых числа ti, di — время начала и продолжительность i-го события.
Формат выходных данных
Выведите одно натуральное число — наибольшее количество событий, в которых Фил может принять участие.
Ограничения
1 ≤ n ≤ 105
0 ≤ ti ≤ 109
1 ≤ di ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 2, получат не менее 20 баллов.
Пояснение к примеру
В примере дано описание трех событий. Фил сможет принять участие в первом и либо во втором, либо в третьем — они частично совпадают по времени.
Два дуэта оперных певцов издавна недолюбливали друг друга. И вот, на церемонии вручения престижной премии "Золотой тенор" их пути пересеклись, накопившееся раздражение вырвалось наружу и было сказано много такого, что вызов на дуэль стал пустой формальностью. В результате обсуждения секундантами условий поединка было решено следующее:
1) Участники дуэли — 4 человека находятся в вершинах квадрата ABCD. Пара из одного дуэта — в вершинах A и C, пара из другого — в B и D.
2) Пистолет каждого из дуэлянтов заряжен одной пулей, стреляют по очереди: A в B, B в C, C в D и D в A. Право первого выстрела определяется жребием.
3) Если кто-то из дуэлянтов выбывает перед своим выстрелом, выстрел делает следующий в очереди. Например, если первым стреляет A и в результате его выстрела B выбывает, то следующим стреляет C.
4) Дуэль завершается, когда все не выбывшие участники сделали по одному выстрелу.
Поединок вызвал огромный интерес в высшем обществе. Газеты пестрели заголовками, а букмекерские конторы принимали ставки на завершение этой необычной дуэли с тем или иным исходом. Помогите рассчитать вероятность завершения дуэли с определенным результатом.
Формат входных данных
Первая строка входного файла содержит четыре натуральных числа, записанных через пробел: a, b, c и d — знаменатели дробей вида 1n, выражающих вероятности попадания участника дуэли в своего соперника. Так, если b = 3, это означает, что B попадет в C с вероятностью 13. Во второй строке расположен один из символов A, B, C или D — результат жребия. Указанный дуэлянт стреляет первым. В третьей строке расположен запрос: строка из четырех символов 0 и 1 — предполагаемый результат дуэли. Например, строка 1001 означает, что в результате поединка невредимыми останутся два участника: A и D. Гарантируется, что дуэль может завершиться указанным образом.
Формат выходных данных
Выведите два натуральных числа — числитель и знаменатель несократимой дроби, выражающей вероятность окончания дуэли с запрошенным исходом.
Ограничения
2 ≤ a, b, c, d ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере даны вероятности попадания участников: A попадет в B с вероятностью 12, B в C с вероятностью 13, C в D с вероятностью 14 и D в A с вероятностью 15. Первым стреляет B. Необходимо узнать, с какой вероятностью дуэль завершится так, чтобы невредимыми остались A и D.
Дуэль должна пройти следующим образом. B попадает в C, тот выбывает и не стреляет в D. D стреляет в A и промахивается. A попадет в B. Дуэль окончена. Вероятность такого развития события составляет 13 × 45 × 12 = 430 = 215.
Тимофей с друзьями занят разработкой новой масштабной многопользовательской онлайн-игры "Мир и война". Процедурно генерируемый открытый мир, обстановка позднего средневековья, дипломатия и алхимия, коварство и любовь, осады замков и странствующие маги, кланы ремесленников и мрачные тюрьмы, пустыни и меняющееся время года — фантазия разработчиков не знает границ.
Прямо сейчас Тимофей разрабатывает квест, пройдя который пользователь игры получит награду — "Бинокль билингвиста". Обладание этим артефактом значительно повышает радиус обзора и позволяет понимать речь Подземного народа. Естественно, ради получения такого мощного предмета игроку придётся попотеть! Ему нужно будет в одиночестве спуститься в подземелье и победить младшего босса, среднего босса и старшего босса, а также несколько мелких врагов. Сражаться с ними придется по очереди, причем их уровень будет подстраиваться под уровень игрока. Тимофей хочет расставить врагов в порядке возрастания их уровней в таком порядке: несколько монстров, младший босс, несколько монстров, средний босс, несколько монстров, старший босс. Причем, если уровень игрока на момент начала квеста равен p, то уровень младшего босса тоже равен p, уровень среднего босса должен быть равен 2 × p, уровень старшего босса должен быть равен 3 × p, а сумма уровней всех врагов в подземелье должна равняться 10 × p. На рисунке внизу Вы видите схему подземелья.
Прежде чем Тимофей приступит к гейм-дизайну этого квеста, помогите ему узнать, сколько есть способов расставить врагов в подземелье?
Формат входных данных
Первая строка входного файла содержит натуральное число p — уровень игрока.
Формат выходных данных
Выведите одно натуральное число — количество способов. Гарантируется, что ответ на задачу не превысит 109.
Ограничения
3 ≤ p ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере есть единственный способ расставить монстров: 1, 3, 4, 6, 7, 9. Сумма всех чисел: 30 = 10 × 3.
Во втором примере есть три способа расставить монстров. Первый: 1, 4, 5, 8, 10, 12. Второй: 1, 4, 6, 8, 9, 12. Третий: 2, 4, 5, 8, 9, 12. Сумма всех чисел в любой расстановке: 40 = 10 × 4.
