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

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

Примеры правильных скобочных последовательностей – «», «()», «((()))», «()()()», «((()())())(())». Неформально говоря, правильная скобочная последовательность – это последовательность скобок, которая может быть получена из некоторого арифметического выражения удалением из него всего, кроме скобок.

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

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

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

Мише исполнилось \(n\) лет. Праздничный торт, испеченный по этому случаю, имеет форму круга радиуса \(r\) с центром в начале координат. На торте стоят \(n\) свечек. Мишина мама разделила торт на части, сделав \(m\) прямолинейных разрезов. Каждый гость взял один из получившихся кусков.

Миша хочет узнать, не досталось ли кому-нибудь из его гостей более одной свечки. Помогите ему это выяснить.

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

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

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

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

Саша и Федя играют в интересную игру. У них есть \(n\) кубиков, на которых написаны различные числа от 1 до \(n\). Ребята нарисовали на бумаге \(n\) клеточек в ряд и играют по следующим правилам.

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

Например, пусть у ребят пять кубиков. Если первый игрок поставил второй и третий кубик на третье и пятое место: «..3.2», то второй игрок может расставить оставшиеся кубики так: «41352». В этом случае первому игроку потребуется сделать пять действий: «41325», «52314», «54132», «54123», «54321», после чего игра закончится.

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