Недавно у градообразующего предприятия города Флатвилля сменилось руководство. Новый генеральный директор не очень-то разбирается в техническом производстве, поэтому заключает все договоры подряд. После этого (чтобы спасти положение) в дело вступает директор по расписаниям, который решает, какие из этих заказов будут выполнены, а за какие придется платить неустойку.

Каждый заказ обладает тремя параметрами: d_i — максимальный номер дня, к которому этот заказ должен быть выполнен; a_i — доход, который получает завод, если выполняет заказ в срок; b_i — неустойка, которую выплачивает завод в случае, если заказ не был выполнен к дню d_i включительно. Нумерация дней ведется со следующего после заключения договоров дня. Известно, что на выполнение одного заказа завод тратит непрерывный отрезок из ровно K дней, причем в один момент времени завод может быть занят только одним заказом.

В итоге перед директором по расписаниям стоит непростая задача: выбрать какие заказы выполнить (и в какое время), а за какие проще сразу заплатить неустойку.

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

В Москве происходит Важное Событие. Посмотреть на Важное Событие съехалось множество людей со всей страны. Во избежание давки и соблюдения порядка полицией была организована очередь, растянувшаяся по набережной Москвы-реки от станции метро X аж до станции метро Y!

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

Раз в секунду через каждую перегородку, перед которой есть хотя бы один человек, в сторону События через турникет пропускают одного человека (то есть из сектора i в сектор i - 1, и из сектора 1 — на само Событие). Внутри сектора люди передвигаются существенно быстрее, поэтому этим временем можно пренебречь.

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

Вася участвовал в недавнем эксперименте: проведи 8 часов без гаджетов. Для того чтобы убить время, он стал проделывать со случайной строкой, состоящей только из нулей и единиц, следующую процедуру. Каждый ноль этой строки он заменял на строку S, тоже состоящую из нулей и единиц, а каждую единицу — на строку T, опять же из нулей и единиц. Строки S и T он выписал заранее. С полученной строкой он опять проделывал ту же самую процедуру, не меняя при этом строки S и T. За 8 часов он успел таким образом сделать K преобразований.

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

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

Белок представляет собой последовательность аминокислот, соединенных пептидной связью (эта связь одинакова между любыми двумя аминокислотами, поэтому рассматриваться она не будет). Аминокислота, как следует из названия, — это органическое соединение, в молекуле которого одновременно содержатся карбоксильные и аминные группы. Для простоты будем считать, что аминокислота состоит из химических элементов, каждый элемент будем обозначать маленькой латинской буквой, таким образом, аминокислота однозначно определяется строкой из нескольких латинских букв. Безусловно, не любая последовательность элементов является аминокислотой.

Для каждого организма известен большой список аминокислот, которые могут быть синтезированы в организме такого типа. Для удобства транскрипции (это один из этапов синтеза РНК), ни одна аминокислота не является началом другой.

Одна из часто встречающихся задач заключается в том, чтобы понять, мог ли данный белок быть синтезирован в данном организме (это позволяет понять по белку, где он был синтезирован: у человека, у гриба и пр.). Для этого нужно проверить, все ли аминокислоты, из которых он состоит, могли быть синтезированы. Однако, часто белок содержит лишние элементы (например, к белку из-за обилия атомов водорода очень часто присоединяются молекулы воды), поэтому задача сводится к изучению фрагментов этого белка. Проводят как отдельные проверки каких-то фрагментов, так и целые серии проверок случайных фрагментов.

Более формально, вам дан словарь из аминокислот, каждая из которых представляет собой строку из маленьких латинских букв, и белóк, который также представляет собой строку из маленьких латинских букв. Необходимо ответить на несколько вопросов вида «мог ли фрагмент белка с позиции l по r быть синтезирован из данных аминокислот», т. е. можно ли данный фрагмент разбить на слова из словаря. В случае положительного ответа, необходимо предъявить минимальное количество слов в таком разбиении.

В новой телевизионной игре участник должен попасть извне в центр системы вложенных крепостей. Каждая крепость представляет собой выпуклый многоугольник, крепости друг друга не касаются. Центральная точка имеет координаты (0, 0) и находится в самой внутренней крепости. Каждая крепость имеет несколько «дверей». Для каждой двери известно время, затрачиваемое на проход через нее. Проходить через крепостную стену вне дверей нельзя. Скорость передвижения участника вне дверей постоянна и равна 1, то есть время передвижения на расстояние S равно S.

Участник изначально находится в одной из дверей внешнего многоугольника (он сам может выбирать, в какой). Его цель — добраться до точки (0, 0) как можно быстрее. Но в игре существует следующее ограничение: когда участник вошел в какую-то дверь, в качестве следующей двери он может выбрать только такую, которая сейчас находится вне зоны его прямой видимости. Если игрок смотрит вдоль стены, то он видит находящиеся в ней двери.

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