#3554

5E: культорги и скобки

Темы: [Разные комбинаторные структуры]

Дана скобочная последовательность. Необходимо определить количество циклических сдвигов, переводящих ее в правильную.

Встретились однажды три культорга ЛКШ...

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

Вам известна скобочная последовательность, записанная первым культоргом. Найдите число, которое произнёс третий культорг.

Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.

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

В единственной строке дана скобочная последовательность, записанная первым культоргом. Длина последовательности не равна нулю и не превышает \(100\,000\) символов.

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

Выведите количество циклических сдвигов, превращающих записанную скобочную последовательность в правильную.

Примеры

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

)(()

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

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

)()(

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

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

()

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

#3555

10E: Pink Floyd

Темы: [Алгоритм Флойда]

Найти самый длинный путь от одной вершины до другой в ориентрованном графе, либо определить, что существует сколь угодно длинный путь, либо определить, что пути не существует.

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

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

Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа \(n\), \(m\) и \(k\) — количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (\(n \le 100\), \(m \le 10\,000\), \(2 \le k \le 10\,000\)). Города пронумерованы числами от \(1\) до \(n\).

Следующие \(m\) строк содержат описание рейсов, по одному на строке. Рейс номер \(i\) описывается тремя числами \(b_i\), \(e_i\) и \(w_i\) — номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (\(1 \le b_i, e_i \le n\), \(-100\,000 \le w_i \le 100\,000\)).

Последняя строка содержит числа \(a_1, a_2, ..., a_k\) — номера городов, в которых проводятся концерты (\(a_i \neq a_{i+1}\)). В начале концертного тура группа находится в городе \(a_1\).

Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число \(l\) — количество рейсов, которые должна сделать группа. Вторая строка должна содержать \(l\) чисел — номера используемых рейсов.

Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку „infinitely kind“.

Примеры

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

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

6
5 6 5 7 2 3

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

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

infinitely kind

#3556

Бинарное дерево (вставка, поиск)

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

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template<class T> void print_tree(Node<T> *p, int level)

{

if(p==NULL)

return;

print_tree(p->left, level+1);

for(int i=0; i<level; i++)

cout << ".";

cout << p->data << endl;

print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

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

ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7

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

DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

#3557

Бинарное дерево (вставка, поиск, удаление)

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

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template<class T> void print_tree(Node<T> *p, int level)

{

if(p==NULL)

return;

print_tree(p->left, level+1);

for(int i=0; i<level; i++)

cout << ".";

cout << p->data << endl;

print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

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

ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE

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

DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5

#3558

Система непересекающихся множеств

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

Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) и обрабатывать запросы таких видов:

RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».

JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.

CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).

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

Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.

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

Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).

Примечание

Ответы «NO» даются на запросы «CHECK 2 11» и «CHECK 9 1», ответ «ALREADY 4 1» — на второй из запросов «JOIN 4 1» (10-я строка), «YES» — на «CHECK 5 10».

Примеры

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

RESET 15
JOIN 14 10
JOIN 13 8
JOIN 0 9
JOIN 8 3
JOIN 4 1
JOIN 10 5
JOIN 8 4
CHECK 2 11
JOIN 4 1
JOIN 2 6
CHECK 9 1
JOIN 6 5
CHECK 10 5

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

RESET DONE
NO
ALREADY 4 1
NO
YES