Васин жесткий диск состоит из \(M\) секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер \(a_i\) и до сектора \(b_i\) включительно, и устанавливал на него очередную систему. При этом если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работающих операционных систем установлено и в настоящий момент работает на Васином компьютере.
Сначала вводятся натуральное число \(M\) — количество секторов на жестком диске (1 ≤ \(M\) ≤ \(10^9\)) и целое число \(N\) — количество разделов, которое последовательно создавал Вася (0 ≤ \(N\) ≤ 100 000).
Далее идут \(N\) пар чисел \(a_i\) и \(b_i\), задающих номера начального и конечного секторов раздела (1 ≤ \(a_i\) ≤ \(b_i\) ≤ \(M\)).
Выведите одно число — количество работающих операционных систем на Васином компьютере.
10 3 1 3 4 7 3 4
1
Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит B рублей.
Вы уже выбрали товар, стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1\), ..., \(d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ.
Как потратить меньше всего денег и получить на дом уже выбранный товар в \(A\) рублей?
Сначала вводятся числа \(A\), \(B\), \(C\), \(N\), а затем \(N\) чисел \(d_1\), ..., \(d_N\).
Все числа целые, 1 ≤ \(A\) ≤ 1000, 1 ≤ \(B\) ≤ 1000, 1 ≤ \(C\) ≤ 1000, 0 ≤ \(N\) ≤ 1000, 1 ≤ \(d_i\) ≤ 1 000 000.
Выведите сначала суммарное количество денег, которое придется потратить. Если при этом вы планируете сделать дополнительный заказ c расчетом на бесплатную доставку, то далее выведите количество этих товаров и их номера в возрастающем порядке. Если же Вы будете оплачивать доставку сами, то далее выведите одно число –1 (минус один).
10 17 25 5 2 7 5 3 7
26 3 1 2 5
В кассовом зале вокзала внедрили систему «электронная очередь». Теперь пассажир, который хочет купить билеты, при входе в зал получает талончик, после чего ожидает, когда подойдет очередь, и его пригласят к освободившейся кассе.
Система «электронная очередь» работает следующим образом. В зале имеются 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-й минуты. Шестому и седьмому пассажиру не остается ничего, кроме как обращаться во вторую кассу. |
Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.
У хозяев курорта имеется топографическая карта территории, высоты на которой отображены с помощью контуров, каждый из которых представляет собой окружность. У каждой окружности указана высота поверхности, прилегающей к внутреннему контуру этой окружности. Вся территория, которая не находится внутри какой-либо окружности, имеет высоту 0. Поскольку это единственная информация о местности, то можно условно считать, что участки между окружностями плоские. Никакие две окружности не пересекаются и не касаются.
Используя эту карту, необходимо проложить санную трассу, которая будет удовлетворять двум условиям: разница высот между начальной и конечной точками должна быть максимальна, и количество пересекаемых контуров не должно превышать некоторого заданного значения \(K\) (это связано с тем, что то место, которым сидят на санках, имеет ограниченную прочность). При этом трасса может иметь участки подъема, но не должна включать в себя ни одной точки, которая была бы выше начальной (туда санки просто не заедут).
На приведенном рисунке пунктирной линией показана наилучшая трасса для \(K\) = 4. Разница высот в ней составляет 68.
Сначала вводятся два натуральных числа \(C\) (1 ≤ \(C\) ≤ 2 000) — количество окружностей и \(K\) (1 ≤ \(K\) ≤ 2 000) – максимальное количество окружностей, которое может пересечь трасса.
Далее идут описания окружностей, каждое из которых состоит из четырех целых чисел: \(X\), \(Y\) (–2000 ≤ \(X\) ≤ 2000, –2000 ≤ \(Y\) ≤ 2000) – координаты центра окружности, \(R\) (1 ≤ \(R\) ≤ 2000) — радиус окружности и \(A\) (–1000 ≤ \(A\) ≤ 1000) — высота местности, касающейся внутреннего края окружности.
Выведите одно число — максимальный перепад высот на трассе.
Пример
| Входные данные | Выходные данные |
| 10 4 38 61 2 73 69 34 3 15 61 59 4 30 40 60 5 66 58 44 6 30 71 34 6 -2 47 21 6 45 41 58 8 52 41 57 11 37 48 40 33 10 | 68 |
В фирме MacroHard работают \(N\) сотрудников, каждый из которых получает зарплату, выражающуюся целым числом рублей. Известно, что ни один сотрудник не получает меньше 5000 рублей, и никто не получает больше 100000 рублей. Также известно, что средняя зарплата сотрудника в этой фирме выражается целым числом копеек и составляет \(A\) рублей \(B\) копеек.
Журналист, готовя публикацию об этой фирме, решил привести зарплаты всех сотрудников. Однако оказалось, что это коммерческая тайна. Журналиста это не смутило, и он решил придумать всем сотрудникам зарплаты. Однако у него возникла сложность – для правдоподобности должны выполняться все общеизвестные ограничения (зарплаты должны выражаться целым числом рублей из диапазона от 5000 до 100000, и вычисление средней зарплаты должно в точности приводить к результату \(A\) рублей \(B\) копеек).
Помогите ему! Напишите программу, которая по введенным числам \(N\), \(A\), \(B\) «придумает» и выведет \(N\) зарплат. Гарантируется, что решение существует.
Вводятся натуральное число \(N\) (1 ≤ \(N\) ≤ 100), натуральное число \(A\) (10000 ≤ \(A\) ≤ 30000) и целое число \(B\) (0 ≤ \(B\) ≤ 99).
Выведите \(N\) целых чисел, выражающих зарплаты сотрудников в рублях. Если возможных вариантов распределения зарплат несколько, выведите любой из них.
5 10000 0
10000 10000 10000 10000 10000