Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Последовательность называется правильной, если она может быть построена по следующим правилам:
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\)-угольников может крайне негативно сказаться на психическом развитии детей, поэтому следует избегать возможности появления в наборе такого множества из \(n\) отрезков, из которых можно составить невырожденный \(n\)-угольник.
Производственная линия сконструирована таким образом, что длины получающихся отрезков могут быть натуральными числами, не превосходящими \(k\). Директор компании хочет, чтобы набор состоял из как можно большего числа отрезков. Ваша задача – построить такой набор.
Входной файл содержит два целых числа: \(n\) – количество вершин в запрещенных многоугольниках и \(k\) – максимальную длину отрезков (3 ≤ \(n\) ≤ 10, 1 ≤ \(k\) ≤ \(10^8\)).
На первой строке выходного файла выведите одно число – наибольшее возможное количество отрезков в наборе, которое может быть достигнуто при данных ограничениях.
На второй строке выведите длины этих отрезков в неубывающем порядке. Если решений несколько, выведите любое.
3 7
5 1 1 2 3 5
Президент одной маленькой, но очень гордой страны вдруг узнал, что на дворе двадцать первый век, и на лошадях ездить уже не модно. Однако, как выяснилось, нефти в стране нет, а без бензина автомобили ездить не умеют. Так что придется закупать нефть в других странах.
Исследование внешнего рынка показало, что в мире есть \(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
Как известно, с целью экономии электроэнергии многие страны используют переход на так называемое летнее время. Перевод времени осуществляется два раза в год – весной и осенью. Весной осуществляется переход на летнее время: часы переводятся на один час вперед. Осенью летнее время отменяется и часы переводятся на один час назад.
Перевод времени осуществляется ночью. При переходе на летнее время через минуту после 01:59 сразу наступает 03:00. При отмене летнего времени час с 02:00 по 02:59 повторяется два раза. А именно, в день перевода, когда первый раз после 02:59 должно стать 03:00, вместо этого снова становится 02:00.
Как одному из разработчиков новой операционной системы «Mocrosoft Widows 2006», вам поручено написать фрагмент ядра операционной системы, который будет осуществлять автоматический перевод системных часов на летнее время и обратно.
По заданным начальному моменту и информации о переводе в текущие и следующие сутки, ваша программа должна вывести показания часов в течение заданного количества минут.
Первая строка входного файла содержит целое число m – количество минут, которое прошло от начала текущих суток, до первого момента времени, который следует вывести. Гарантируется, что оно неотрицательно и строго меньше числа минут в текущих сутках.
На второй строке находятся два целых числа \(d_1\) и \(d_2\), которые указывают, какой перевод времени осуществляется в текущие и в следующие сутки. Значение 1 означает, что осуществляется переход на летнее время, -1 означает, что осуществляется отмена летнего времени, а 0 означает, что перевода времени не осуществляется.
На третьей строке записано число \(k\) – количество отсчетов времени, которое ваша программа должна вывести (1 ≤ \(k\) ≤ 600).
Выходной файл должен состоять из \(k\) строк, \(i\)-я из которых должна содержать показания часов через (\(i\)-1) минут после начального момента времени. Выводите время в формате «hh:mm».
118 1 0 4
01:58 01:59 03:00 03:01
190 -1 0 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