Слова в языке Мумба-Юмба могут состоять только из букв \(a\), \(b\) и при этом:
* никогда не содержат двух букв \(b\) подряд,
* ни в одном слове никогда не встречается три одинаковых подслова подряд. Например, по этому правилу в язык Мумба-Юмба не могут входить слова aaa (так как три раза подряд содержит подслово a), ababab (так как три раза подряд содержит подслово ab), aabababa (также три раза подряд содержит подслово ab).
Все слова, удовлетворяющие вышеописанным правилам, входят в язык Мумба-Юмба.
Напишите программу, которая подсчитает количество слов длины ровно \(K\) символов в языке племени Мумба-Юмба.
Вводится одно число \(K\) (1 ≤ \(K\) ≤ 100 000)
Выведите одно число — количество слов в этом языке длины \(K\).
Васин жесткий диск состоит из \(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 |