---> 27 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
3
AAB
Выходные данные
ABA
Входные данные
6
QAZQAZ
Выходные данные
AQZZQA
Входные данные
6
ABCDEF
Выходные данные
A
Задана таблица, содержащая буквы, а также набор слов, которые необходимо вычеркнуть. Каждая следующая буква слова содержится в таблице рядом с предыдущей. Требуется вычеркнуть все слова из таблицы и вывести оставшиеся буквы.

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера NxN, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке ниже показано, как может быть расположено в таблице слово olympiad.

P

O

L

T

E

R

W

Y

M

S

O

A

I

P

T

B

D

A

N

R

L

E

M

E

S

Когда Петя находит слово, он вычеркивает его из таблицы. Использовать уже вычеркнутые буквы в других ключевых словах нельзя.

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

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

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

В первой строке входного файла записаны два числа N (1N10) и M (0M200). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 200 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.

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

В единственную строку выходного файла выведите в любом порядке буквы, которые останутся в таблице.

Примеры
Входные данные
5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST
Выходные данные
AENRSW
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

Требуется привести любую из допустимых раскрасок.

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

В первой строке записано одно число N (4N100) - количество вершин многоугольника.

Далее следуют N–3 строки, в каждой из которых записана пара натуральных чисел — номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.

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

В выходном файле должны быть 2N–3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.

Примеры
Входные данные
4
1 3
Выходные данные
Входные данные
6
1 3
3 5
5 1
Выходные данные
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Купцы хотят продать шаху n драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет. Видов драгоценных камней на Востоке известно не очень много всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. Он заранее определил несколько упорядоченных пар типов камней: ($a_1$, $b_1$), ($a_2$, $b_2$), ..., ($a_k$, $b_k$). Эти пары он называет красивыми, их множество мы обозначим как P. Теперь представим ряд камней, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i,j), что 1 ≤ i < j ≤ n, а камни $S_i$ и $S_j$ образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k, что $S_i = a_q$ и $S_j = b_q$.

Если число таких пар оказывается достаточно большим, то шах покупает все камни. Однако в этот раз купцы привезли настолько много камней, что шах не может посчитать это число. Поэтому он вызвал своего визиря и поручил ему этот подсчет. Напишите программу, которая находит ответ на эту задачу.

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

Первая строка входного файла содержит целые числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 676) число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую типы камней, которые привезли купцы.

Далее следуют k строк, каждая из которых содержит две строчных буквы латинского алфавита и описывает одну из красивых пар камней.

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

В выходной файл выведите ответ на задачу — количество пар, которое должен найти визирь.

Примеры
Входные данные
7 1
abacaba
aa
Выходные данные
6
Входные данные
7 3
abacaba
ab
ac
bb
Выходные данные
7

Страница: << 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест