#591

Триангуляция

Темы: [Сортировка подсчетом] [Сканирующая прямая]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 1 день, Задача A ]

Вася нарисовал выпуклый \(N\)-угольник и провел в нем несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри \(N\)-угольника. Теперь он утверждает, что весь \(N\)-угольник оказался разбит на треугольники. Напишите программу, которая проверяет истинность Васиного утверждения.

Входные данные

Сначала вводятся числа \(N\) - количество вершин \(N\)-угольника (3 <= \(N\) <= 1000) и \(M\) - количество диагоналей, проведенных Васей. Далее на вход программы поступают \(M\) пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри \(N\)-угольника. Вершины \(N\)-угольника нумеруются числами от 1 до \(N\).

Выходные данные

Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число \(K\) - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено \(K\) чисел - номера вершин исходного \(N\)-угольника, которые являются вершинами этой \(K\)-угольной части в порядке обхода этой части.

Примеры

Входные данные

3
0

Выходные данные

Входные данные

4 1
1 3

Выходные данные

Входные данные

6 2
1 3
5 3

Выходные данные

4 1 3 5 6

#592

Палиндром

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 1 день, Задача B ]

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.

На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.

Входные данные

В первой строке входных данных содержится число \(N\) (1 <= \(N\) <= 100000). Во второй строке задается последовательность из \(N\) больших латинских букв (буквы записаны без пробелов).

Выходные данные

В единственной строке выходных данных выдайте искомый палиндром.

Группы тестов

25 баллов — (1 ≤ N ≤ 10) .

25 баллов — (1 ≤ N ≤ 1 000 ) .

50 баллов — полные ограничения.

Примечание

Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!

Примеры

Входные данные

3
AAB

Выходные данные

ABA

Входные данные

6
QAZQAZ

Выходные данные

AQZZQA

Входные данные

6
ABCDEF

Выходные данные

#593

Представление числа

Темы: [Динамическое программирование на таблицах]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 1 день, Задача C ]

Учительница математики попросила школьников составить арифметическое выражение так, чтобы его значение было равно данному числу \(N\), и записать его в тетради. В выражении могут быть использованы натуральные числа, не превосходящие \(K\), операции сложения и умножения, а также скобки. Петя очень не любит писать, и хочет придумать выражение, содержащее как можно меньше символов. Напишите программу, которая поможет ему в этом.

Входные данные

В первой строке входных данных содержатся два натуральных числа: \(N\) (1 <= \(N\) <= 10000) - значение выражения и \(K\) (1 <= \(K\) <= 10000) - наибольшее число, которое разрешается использовать в выражении.

Выходные данные

В единственной строке выведите выражение с данным значением, записывающееся наименьшим возможным количеством символов. Если решений несколько, выведите любое из них.

Примечание

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

Примеры

Входные данные

7 3

Выходные данные

5
3+1+3

Входные данные

15 20

Выходные данные

2
15

Входные данные

176 1

Выходные данные

41
(1+1+1+1)*(1+1+1+1)*(1+1+(1+1+1)*(1+1+1))

#594

Восстанови многоугольник

Темы: [Двумерные массивы] [Клеточная геометрия]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 1 день, Задача D ]

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

Восстановите нарисованный Васей многоугольник.

Входные данные

В первой строке входных данных содержатся два натуральных числа: \(Y\) - количество строк и \(X\) - количество столбцов листа (3 <= \(Y\) <= 1000, 3 <= \(X\) <= 1000). В каждой из следующих \(Y\) строк задается по \(X\) целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.

Выходные данные

Выведите искомый многоугольник в следующем формате.

Выходные данные должны содержать \(Y\) строк по 2\(X\)-1 символов в каждой (по одному символу на клетку и линию между клетками).

В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.

Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.

Примеры

Входные данные

Выходные данные

...._..
.._|.|.
.|_._|.
.......