На клетчатой плоскости закрашено K клеток. Требуется найти минимальный по площади прямоугольник, со сторонами, параллельными линиям сетки, покрывающий все закрашенные клетки.
Во входном файле, на первой строке, находится число K(1 ≤ K ≤ 100). На следующих K строках находятся пары чисел Xi и Yi – координаты закрашенных клеток (|Xi|, |Yi| ≤ 109).
Выведите в выходной файл координаты левого нижнего и правого верхнего углов прямоугольника.
3 1 1 1 10 5 5
1 1 5 10
Строки формируются по правилу: S1 = a, Si = Si-1 + chr(i) + Si-1. Необходимо по данной строке найти максимальное i, такое что данная строка является подстрокой Si
Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .
После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.
Астрономы (в знак благодарности) нашли какую-то отдалённую звезду с огромной статуей динозавра, похожего на земные аналоги. Экспедиция, посетившая указанную звезду, нашла под статуей надпись, очевидно, с кодом этого динозавра. Впрочем, часть надписи стёрлась. Теперь учёные хотят максимально завысить древность находки. Для этого нужно определить, в коде динозавров какой эпохи – самой древней из подходящих – встречается данный образец (как подстрока). Такую задачу не по силам решить даже астрономам.
На первой и единственной строке входного файла находится непустая строка, состоящая из символов `a', …, `z', `0', …, `9'. Длина строки не превосходит 100.
Выведите два числа – номер эпохи и смещение образца от начала кода. Если же статуя изображает неземного динозавра (или код инопланетян отличается от земного), выведите в выходной файл число 0.
a
1 0
bae
5 13
Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(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\) стран, экспортирующих нефть. При этом \(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