Задача A. Скобки ≡

Условие

Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Последовательность называется правильной, если она может быть построена по следующим правилам:

• пустая строка является правильной скобочной последовательностью;
• если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.
• если A и B — правильные скобочные последовательности, то AB — тоже правильная скобочная последовательность.

Рассмотрим последовательность скобок, содержащую как круглые, так и квадратные скобки. Пусть разрешается выполнять следующие операции: заменить открывающуюся квадратную скобку на произвольное число открывающихся круглых и заменить закрывающуюся квадратную скобку на произвольное количество закрывающихся круглых. Разрешается при замене создавать ноль скобок, то есть просто удалять соответствующую квадратную скобку.

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

Например, из строки [)())(]()] можно получить правильную скобочную последовательность (()())()().

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

[)())(]()]

(()())()()

[]

[)(][]

()()

())

Impossible

Задача C. N-угольники ≡

Условие

Один из известных производителей товаров для детей во Флатландии собирается выпустить на рынок новую развивающую игру. Набор для игры будет состоять из некоторого количества отрезков, из которых дети смогут складывать различные фигуры.

Однако на презентации нового продукта перед государственной комиссией один из специалистов указал на то, что составление невырожденных n-угольников может крайне негативно сказаться на психическом развитии детей, поэтому следует избегать возможности появления в наборе такого множества из n отрезков, из которых можно составить невырожденный n-угольник.

Производственная линия сконструирована таким образом, что длины получающихся отрезков могут быть натуральными числами, не превосходящими k. Директор компании хочет, чтобы набор состоял из как можно большего числа отрезков. Ваша задача — построить такой набор.

Формат входного файла

Формат выходного файла

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

На второй строке выведите длины этих отрезков в неубывающем порядке. Если решений несколько, выведите любое.

Ограничения

Примеры тестов

3 7

5
1 1 2 3 5

Задача D. Нефть ≡

Условие

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

Исследование внешнего рынка показало, что в мире есть n стран, экспортирующих нефть. При этом i-е государство продает баррель нефти либо за a_i долларов, либо за b_i евро.

У президента есть a долларов и b евро. Главный бухгалтер утверждает, что если попытаться купить нефть у одного государства и за доллары, и за евро, то бюрократия может надолго отложить покупку, чего президент, разумеется, не хочет.

Помогите президенту в таких непростых условиях узнать, сколько баррелей нефти он сможет купить.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 2 5
6 4
3 5
8 7

1.92

4 3 2
1 1
2 2
3 3
4 4

4.00

Задача G. Головоломка ≡

Условие

Не так давно были достаточно популярны настольные игры на больших бумажных картах, в которых игроки передвигали фишки по определенным правилам.

Недавно Вася нашел на чердаке целую кипу таких карт, но к ним, к сожалению, не прилагались правила игры. Без описаний он смог только понять, что на каждой из карт нарисовано некоторое количество кружков — возможных позиций для фишки, среди которых выделены начальная и конечная. Какие-то кружки соединены между собой отрезками, по которым разрешается перемещать фишку, при этом между некоторыми парами кружков может быть проведено сразу несколько отрезков. Перемещать фишку по отрезку разрешается в обоих направлениях.

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

Вася заинтересовался, за какое минимальное количество ходов можно добиться того, чтобы фишки на всех картах одновременно оказались в конечных позициях. Помогите ему это выяснить.

Гарантируется, что в пределах каждой карты из любой позиции можно переместить фишку в любую другую, возможно через некоторые промежуточные позиции.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2
5 4
1 2
2 3
3 4
3 5
3 3
1 2
2 3
3 1

3

Задача H. Экспериментатор ≡

Условие

На старости лет один профессор загорелся идеей исследования на прочность транзисторов "КД521(2)". К сожалению, ему не удалось привлечь на помощь никого из коллег, поэтому проводить измерения придется самостоятельно. Но это не пугает профессора.

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

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

Известно, что все транзисторы абсолютно одинаковые, и если транзистор разбивается при падении с некоторого этажа, то он разбивается и при падении со всех этажей с большим номером.

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

Годы профессора уже дают о себе знать, поэтому он хочет минимизировать суммарное расстояние, которое ему придется подниматься по лестнице. Но, возраст дает и определенные преимущества — сняв очки, профессор может с любого этажа определить, разбился транзистор или нет.

Изначально профессор находится на первом этаже, и у него имеется m транзисторов. В доме, в котором живет профессор, n этажей.

Найдите минимальное число этажей, которое профессору в худшем случае придется подниматься вверх по лестнице во время проведения экспериментов.

В первом из приведенных примеров оптимальное поведение профессора следующее. Сначала следует подняться на два этажа и бросить транзистор с третьего. Если транзистор разобьется, то следует спуститься на второй этаж и попытаться бросить транзистор оттуда — если транзистор разбивается и при бросании со второго этажа, то результат 2, иначе — 3. Если же транзистор не разобьется при падении с третьего этажа, то придется подняться на четвертый и бросить транзистор оттуда. Если он разобьется, то результат 4, если нет — 5. В худшем случае придется подняться на три этажа.

Во втором примере ничего бросать не надо, результат исследования — 2.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5 2

3

2 2

0

Задача I. Перевод времени ≡

Условие

Как известно, с целью экономии электроэнергии многие страны используют переход на так называемое \emph{летнее время}. Перевод времени осуществляется два раза в год — весной и осенью. Весной осуществляется переход на летнее время: часы переводятся на один час вперед. Осенью летнее время отменяется и часы переводятся на один час назад.

Перевод времени осуществляется ночью. При переходе на летнее время через минуту после 01:59 сразу наступает 03:00. При отмене летнего времени час с 02:00 по 02:59 повторяется два раза. А именно, в день перевода, когда первый раз после 02:59 должно стать 03:00, вместо этого снова становится 02:00.

Как одному из разработчиков новой операционной системы Mocrosoft Widows 2006, вам поручено написать фрагмент ядра операционной системы, который будет осуществлять автоматический перевод системных часов на летнее время и обратно.

По заданным начальному моменту и информации о переводе в текущие и следующие сутки, ваша программа должна вывести показания часов в течение заданного количества минут.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

118
1 0
4

01:58
01:59
03:00
03:01

190
-1 1
1

02:10

0
-1 0
3

00:00
00:01
00:02

1438
0 1
4

23:58
23:59
00:00
00:01