Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.
Первая строка входного файла содержит числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 200). Следующие \(m\) строк содержат описание рисунка. Каждая строка содержит ровно \(n\) символов. Символ «.» обозначает пустой квадрат, а символ «#» – закрашенный.
Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.
Если же этого сделать нельзя, выведите в выходной файл «NO».
2 1 # .
NO
2 2 .. ##
YES .. ab
1 3 ###
YES abb
3 1 . # #
YES . a b
Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Последовательность называется правильной, если она может быть построена по следующим правилам:
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
На город Энск нападает флот инопланетян. Флот состоит из n космических кораблей, каждый из которых имеет форму равнобедренного прямоугольного треугольника.
Носом инопланетного корабля считается вершина, угол при которой прямой, а осью корабля называется высота, опущенная на гипотенузу.
Флот инопланетян прилетел с северо-востока, и застыл в таком положении, что все оси кораблей направлены строго на юго-запад.
Единственный способ нанести урон инопланетной армии – это пустить из некоторой точки поверхности Земли лазерный луч вертикально вверх. Пущенный так луч прожигает насквозь все вражеские корабли, через которые он проходит (даже те, которые он задевает по границе). Но этот выстрел повредит инопланетянам только в случае, если все n кораблей будут при этом поражены.
Военные власти города Энска решили нанести удар по вражеским войскам. Для этого решено поставить лазеры в одну из точек, над которыми находятся все n вражеских кораблей.
Помогите военным определить площадь территории, на которой можно поставить лазер.
В первой строке входного файла содержится целое число \(n\) – количество инопланетных кораблей (1 ≤ \(n\) ≤ 100).
В каждой из следующих n строк описывается положение очередного корабля. Описание состоит из трех целых чисел \(x_i\), \(y_i\) и \(s_i\), где \(x_i\) и \(y_i\) – координаты носа, а \(s_i\) – размер корабля. Поскольку корабль имеет форму равнобедренного прямоугольного треугольника, размером корабля военные решили называть длину катета.
Размеры кораблей – положительные числа, не превышающие 1 000. Координаты носов кораблей не превышают по абсолютной величине \(10^5\).
В выходной файл выведите площадь территории, над которой находятся все инопланетные корабли. Выведите ответ с точностью до трех знаков после десятичной точки.
3 2 4 6 4 2 7 3 3 5
4.500