--->
78 задач
<---
Источники
Сегодня на уроке физики рассказывали удивительные вещи. Придя домой, Витя решил проверить слова учителя о том, что если взять два одинаковых сосуда, соединенных тонкой трубкой на уровне основания, то уровень жидкости при любом ее количестве также будет одинаковым для обоих сосудов.
Способ убедиться в правильности утверждения Витя избрал довольно оригинальный. Он взял аквариум с основанием длиной N и шириной 1, очень высокими стенками, и поставил N –1 перегородку параллельно узкой боковой стенке аквариума, тем самым, разделив аквариум на N одинаковых отсеков. Каждая перегородка имеет ширину 1 и очень большую высоту. Толщиной перегородки можно пренебречь. В каждой из перегородок есть точечное отверстие на высоте Hi, диаметром которого также можно пренебречь. После всех этих приготовлений Витя медленно наливает в первый отсек (между стенкой и 1ой перегородкой) C литров воды. В часть аквариума размером 1x1x1 вмещается ровно один литр воды. Так как стенки и перегородки в аквариуме были очень высокими, то через край вода не переливалась. После установления стационарного состояния он замерил уровень жидкости в каждом из N сосудов.
Теперь он хочет убедиться, что его экспериментальные данные не опровергают законы, рассказанные на уроке. Он обратился к вам с просьбой выяснить, какой должна быть высота жидкости в каждом из сосудов с теоретической точки зрения.
Рассмотрим подробно случай N = 3. Пусть сначала H1 < H2. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вода станет поступать во второй отсек до тех пор, пока уровни в обоих отсеках не сравняются (или уровень воды в первом отсеке окажется равным H1, тогда во втором отсеке он будет на уровне С – H1). Далее уровень жидкости в первых двух частях будет увеличиваться равномерно (или не будет меняться). Как только вода достигнет второго отверстия, вся она будет поступать в третий отсек, опять же до тех пор, пока уровни жидкости во всех трех частях не сравняются или вода в первых двух отсеках достигнет уровня H2. После этого, если воды оказалось достаточно, весь аквариум будет заполняться равномерно.
Пусть теперь H1 > H2. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вся вода станет поступать во второй отсек. Если после этого уровень во втором отсеке сравняется с уровнем второго отверстия, то вода станет выливаться в третий до тех пор, пока высоты жидкостей во втором и третьем отсеках не станут равными. Далее уровень воды в них будет равномерно увеличиваться, пока не достигнет первого отверстия. После этого весь аквариум будет заполняться равномерно.
В первой строке записаны целые N и C (1 ≤ N ≤ 100000, 0 ≤ C ≤ 2*109). В следующих N –1 строках содержится по одному целому числу Hi (0 ≤ Hi ≤ 2*109), обозначающему высоту отверстия в i-й перегородке.
Выведите N чисел, каждое на новой строке, с точностью до шести знаков после десятичной точки —уровень жидкости в 1, 2, ..., N отсеке соответственно.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 100. Оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N ≤ 10000. Оценивается в 30 баллов.
4 4 3 2 1
3.00000000000000000000 1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
4 10 1 2 3
3.00000000000000000000 3.00000000000000000000 3.00000000000000000000 0.99999999999999911000
Месклиниты собрались в экспедицию на край света. У них есть корабль, состоящий из N × M плотиков, связанных между собой. У каждого плотика есть своя грузоподъемность, а у каждого месклинита – своя масса. На каждом плотике может находиться не более одного месклинита. Если грузоподъемность выбранного плотика меньше массы месклинита, то бедный месклинит утонет при посадке.
Руководитель экспедиции продумывает рассадку по плотикам. Помогите ему определить, какому максимальному количеству месклинитов удастся отправиться в путь.
В первой строке даны числа N и M (1 ≤ N, M ≤ 40). В каждой из последующих N строк содержится по M чисел, обозначающих грузоподъемность соответствующего плотика. В (N+2)-ой строке находится число K (1 ≤ K ≤ 2000) – количество месклинитов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – масса i-ого месклинита. Все массы месклинитов и грузоподъемности плотиков – натуральные числа, не превышающие 109.
Требуется вывести одно число – максимально возможное количество участников экспедиции.
3 2 5 10 7 5 5 5 6 9 5 3 5 12 10
4
В кассовом зале вокзала внедрили систему «электронная очередь». Теперь пассажир, который хочет купить билеты, при входе в зал получает талончик, после чего ожидает, когда подойдет очередь, и его пригласят к освободившейся кассе.
Система «электронная очередь» работает следующим образом. В зале имеются N касс, которые работают все время, за исключением времени перерывов (время перерывов в каждой кассе свое). Пассажиры приглашаются к кассам строго в порядке получения ими талончиков. Каждый пассажир проводит у кассы 5 минут (которые уходят на выбор поезда и оплату заказа), плюс оформление каждого билета дополнительно занимает еще одну минуту (таким образом, если пассажир, например, хочет оформить 3 билета, то он проведет у кассы 8 минут). Если пассажир был приглашен к кассе в момент времени A, а оформление его займет K минут, то и он, и эта касса освободятся к моменту времени A+K+1.
В освободившуюся кассу направляется очередной покупатель, если только в этой кассе не должно быть перерыва в ближайшие 5 минут. Но если касса начала оформление заказа какого-то пассажира, то она завершает оформление этого заказа, даже если в ней в процессе оформления должен начаться перерыв. При этом перерыв не сдвигается (то есть начинается на некоторое время позднее, но заканчивается ровно во столько, во сколько и должен). Считается, что если перерыв в кассе с момента A до момента B, то касса, освобождаясь в момент (A–5) начинает обслуживание очередного покупателя, а освобождаясь в моменты (A–4), (A–3), и так далее, — не начинает, а первого покупателя после перерыва касса начнет обслуживать в момент (B+1).
Если одновременно освобождается сразу несколько касс, то первый по очереди попадает в кассу с меньшим номером, второй — в следующую и т.д. Если в момент, когда касса освобождается, в очереди нет пассажиров, касса, естественно, никого не обслуживает. В этом случае, как только новый пассажир приходит и встает в очередь, он тут же попадает на обслуживание в свободную кассу с минимальным номером.
Напишите программу, которая по информации о времени прихода каждого пассажира и о количестве билетов, которые он собирается купить, выведет время, когда этот пассажир покинет кассовый зал.
Ни один пассажир не покупает больше 10 билетов, никакие два пассажира не приходят в кассовый зал в один и тот же момент времени, между концом одного перерыва и началом следующего перерыва у одной кассы проходит не менее 60 минут, длительность каждого перерыва не менее 15 минут.
Сначала вводятся количество касс \(N\) и и количество пассажиров \(M\) (1 ≤ \(N\) ≤ 30, 1 ≤ \(M\) ≤ 10000). Далее идет описание перерывов каждой кассы: оно начинается с числа \(C_k\) (1 ≤ \(k\) ≤ \(N\)) — количество перерывов у данной кассы (0 ≤ \(C_k\) ≤ 5), а далее идут \(C_k\) пар чисел, задающих время начала перерыва и его длительность. Перерывы каждой кассы перечислены в порядке наступления.
Далее заданы \(M\) пар чисел, задающих время прихода очередного пассажира и количество билетов, которые он собирается купить. Пассажиры перечислены в порядке их прихода.
Все времена и длительности — натуральные числа, не превышающие 100000.
Для каждого пассажира выведите два числа — номер кассы, которая будет его обслуживать, и время, в которое он покинет кассовый зал, купив нужные ему билеты.
Примеры
| Вход | Выход | Комментарий |
| 1 2 1 10 15 1 1 2 2 | 1 7 1 32
| Имеется единственная касса с перерывом с 10-ю по 24-ю минуты. Первый пассажир будет сразу обслужен, его оформление закончится в 7 минут. За это время придет второй пассажир, однако до перерыва единственной кассы останется 3 минуты, поэтому она не будет никого принимать до его окончания. Второй пассажир будет принят только на 25 минуте и освободится в 32. |
| 2 7 2 10 15 305 15 1 5 15 1 1 2 2 100 3 101 1 300 1 301 1 302 1 | 1 7 2 27 1 108 2 107 1 306 2 307 2 313 | Первый пассажир сразу пойдет в первую кассу, она оформит его к 7-й минуте и не будет никого принимать до 25-й минуты в связи с перерывом. По той же причине вторая касса не сможет никого принять до окончания ее перерыва. На 20-й минуте к ней поступит второй пассажир. К 100-й минуте обе кассы будут свободны, поэтому пришедших в 100-ю и 101-ю минуты сразу пригласят к кассам (третьего – к минимальной по номеру свободной). На 300-й минуте пятый пассажир начнет оформляться в первой кассе, после чего она сразу закроется на перерыв до 320-й минуты. Шестому и седьмому пассажиру не остается ничего, кроме как обращаться во вторую кассу. |
Рассмотрим числовую последовательность \(a_1\), ..., \(a_N\). Мы будем называть подстроку \(a_i\), …, \(a_j\), ..., \(a_k\) (1 \(\le\) \(i\) < \(j\) < \(k\) \(\le\) \(N\)) исходной последовательности холмом, если \(a_t\) < \(a\)t+1 для любого \(i\) \(\le\) \(t\) < \(j\) и \(a_t\) > \(a\) t+1 для любого \(j\) \(\le\) \(t\) < \(k\). В таком случае вершиной холма считается min{\(j\) − \(i\), \(k\) − \(j\)} . Аналогично, мы будем называть подстроку долиной, если \(a_t\) > \(a\)t+1 для любого \(i\) \(\le\) \(t\) < \(j\) и \(a_t\) < \(a\)t+1 для любого \(j\) \(\le\) \(t\) < \(k\). Тогда глубиной долины будет считаться min{\(j\)-\(i\), \(k\)-\(j\)}. Вычислите высоту самого высокого холма и глубину самой глубокой долины в данной последовательности.
В первой строке входного файла находится число \(T\) (1 \(\le\) \(T\) \(\le\) 100000) — количество тестовых блоков. Далее располагаются тестовые блоки, занимающие по 2 строки. Первая из двух строк содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 1000000), во второй строке находятся члены последовательности, разделенные пробелом. Сумма значений \(N\) всех тестовых блоков в файле не превышает 100 000. Абсолютные значения членов последовательности не превышают 1 000 000.
Выходной файл должен состоять из \(T\) строк, в каждой строке по 2 числа: высота высочайшего холма и глубина самой глубокой долины. Если в тестовом блоке не существует долин или холмов, выведите число 0.
2 10 4 4 1 6 3 2 1 2 5 7 10 2 3 4 5 6 7 8 9 10 9
1 3 1 0
Возвращаясь с турслета, Вася пришел на станцию и хочет уехать в Москву. На станции не оказалось расписания электропоездов, но у Васи есть справочник, в котором указано время отправления поездов с конечных пунктов, а также время следования от каждого из конечных пунктов до станции, где находится Вася.
Помогите Васе определить, сколько ему придется ждать ближайшую электричку.
Сначала вводятся два числа, задающих часы и минуты прихода Васи на станцию.
Далее идет число \(N\) — количество конечных станций, от которых отправляются электрички, проходящие через Васину станцию (1≤\(N\)≤100).
Далее идет N блоков данных (по одному блоку для каждой станции). Сначала записано время \(T_i\) следования электрички от станции ее отправления до станции, где находится Вася. Время задается в минутах и выражается целым неотрицательным числом, не превышающим 1440.
Далее идет число \(M_i\), определяющее количество электричек в сутки, отправляющихся от этой станции (1≤\(M_i\)≤100). Далее идет \(M_i\) пар чисел, задающих времена отправления электричек от этой станции. Все времена указаны в возрастающем порядке.
Часы находятся в интервале от 0 до 23, минуты – от 0 до 59.
Считается, что все электропоезда ходят ежедневно. Т.е., например, если у нас только один пункт и только одна электричка, и с этого пункта она отправляется в 23.59 и идет до Васиной станции 61 минуту, то в 01.00 Вася может на ней уехать в тот день, когда он пришел на станцию (если он пришел не позднее 01.00), или на следующий день, если он придет позднее.
Гарантируется, что хотя бы одна электричка в сутки через Васину станцию проходит.
Выведите одно число — время в минутах, которое Васе придется ждать ближайшую электричку. Считается, что если Вася и электричка приходят на станцию одновременно, то Вася успевает на эту электричку и время ожидания 0.
15 57 2 5 2 15 50 19 30 30 1 15 43
16
18 0 1 0 1 15 0
1260
18 0 2 0 1 18 0 10 1 17 50
0