Страница: 1 Отображать по:
#591
Триангуляция
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
3
0
Выходные данные
0
Входные данные
4 1
1 3
Выходные данные
0
Входные данные
6 2
1 3
5 3
Выходные данные
4 1 3 5 6
#592
Палиндром
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке входных данных содержится число \(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
Выходные данные
A
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест