Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Последовательность называется правильной, если она может быть построена по следующим правилам:
1. пустая строка является правильной скобочной последовательностью; 2. если S – правильная скобочная последовательность, то (S) – тоже правильная скобочная последовательность. 3. если A и B – правильные скобочные последовательности, то AB – тоже правильная скобочная последовательность.
Примеры правильных скобочных последовательностей – «», «()», «((()))», «()()()», «((()())())(())». Неформально говоря, правильная скобочная последовательность – это последовательность скобок, которая может быть получена из некоторого арифметического выражения удалением из него всего, кроме скобок.
Рассмотрим последовательность скобок, содержащую как круглые, так и квадратные скобки. Пусть разрешается выполнять следующие операции: заменить открывающуюся квадратную скобку на произвольное число открывающихся круглых и заменить закрывающуюся квадратную скобку на произвольное количество закрывающихся круглых. Разрешается при замене создавать ноль скобок, то есть просто удалять соответствующую квадратную скобку.
Требуется с использованием указанных операций получить из заданной строки минимальную по длине правильную скобочную последовательность, состоящую только из круглых скобок.
Например, из строки [)())(]()] можно получить правильную скобочную последовательность (()())()().
Входной файл содержит одну строку, состоящую только из круглых и квадратных скобок. Длина строки не превышает 2000 символов.
Выведите в выходной файл минимальную по длине правильную скобочную последовательность из круглых скобок, которую можно получить из заданной строки описанными операциями. Если решений несколько, выведите любое. Если из данной строки нельзя получить ни одной правильной скобочной последовательности, выведите в выходной файл слово «Impossible».
[)())(]()]
(()())(())
[)(][]
()()
())
Impossible
Мише исполнилось \(n\) лет. Праздничный торт, испеченный по этому случаю, имеет форму круга радиуса \(r\) с центром в начале координат. На торте стоят \(n\) свечек. Мишина мама разделила торт на части, сделав \(m\) прямолинейных разрезов. Каждый гость взял один из получившихся кусков.
Миша хочет узнать, не досталось ли кому-нибудь из его гостей более одной свечки. Помогите ему это выяснить.
Первая строка входного файла содержит целые числа \(n\), \(m\) и \(r\) (1 ≤ \(n\) ≤ 10000, 0 ≤ \(m\) ≤ 1000, 1 ≤ \(r\) ≤ 2000).
Следующие n строк содержат пары целых чисел \(x_i\), \(y_i\) – координаты точек, где расположены свечки. Гарантируется, что эти точки лежат внутри круга, размерами свечек следует пренебречь. Никакие две свечки не совпадают.
Последние \(m\) строк содержат описание разрезов – тройки целых чисел \(a_i\), \(b_i\), \(c_i\). Такая тройка соответствует разрезу, который задается уравнением \(a_i\) \(x\) + \(b_i\) \(y\) + \(c_i\) = 0. Ни один разрез не проходит через свечку. Никакие два разреза не совпадают. Числа ai, bi, ci не превышают 10000 по модулю.
Если одному из гостей досталось более одной свечки, выведите в выходной файл слово «YES», иначе выведите слово «NO».
3 2 3 2 2 1 -1 -2 0 2 -1 0 0 1 -1
NO
3 2 3 2 2 1 -1 -2 0 1 1 -1 0 1 -1
YES
4 2 10 1 1 1 -1 -1 1 -1 -1 0 1 0 1 0 0
NO
Президент одной маленькой, но очень гордой страны вдруг узнал, что на дворе двадцать первый век, и на лошадях ездить уже не модно. Однако, как выяснилось, нефти в стране нет, а без бензина автомобили ездить не умеют. Так что придется закупать нефть в других странах.
Исследование внешнего рынка показало, что в мире есть \(n\) стран, экспортирующих нефть. При этом \(i\)-е государство продает баррель нефти либо за \(a_i\) долларов, либо за \(b_i\) евро.
У президента есть \(a\) долларов и \(b\) евро. Главный бухгалтер утверждает, что если попытаться купить нефть у одного государства и за доллары, и за евро, то бюрократия может надолго отложить покупку, чего президент, разумеется, не хочет.
Помогите президенту в таких непростых условиях узнать, сколько баррелей нефти он сможет купить.
На первой строке входного файла записаны три целых числа: \(n\), \(a\) и \(b\) (1 ≤ \(n\) ≤ 100, 0 ≤ \(a\), \(b\) ≤ 1000). В последующих \(n\) cтроках содержатся пары чисел \(a_i\), \(b_i\) (1 ≤ \(a_i\), \(b_i\) ≤ 1000).
Выведите в выходной файл максимальное количество нефти, которое может купить президент. Выведите ответ не менее чем с двумя знаками после десятичной точки.
3 2 5 6 4 3 5 8 7
1.91666666666667E+0000
4 3 2 2 4 3 2 4 1 3 3
3.50000000000000E+0000