Вася нарисовал выпуклый \(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
Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.
На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.
В первой строке входных данных содержится число \(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
Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.
Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.
Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.
280138
798081
8810
123
456
-1
Online-группа тестов оценивается в 60 баллов, в этой группе числа A и B содержат не более 1000 цифр каждое. При этом решения, правильно работающие для случая, когда A и B содержат не более 6 цифр, будут оценены не менее, чем в 20 баллов. Решения, правильно работающие для случая, когда A и B содержат не более 9 цифр, будут оценены не менее, чем в 40 баллов.
Offline-группа тестов оценивается в 40 баллов.