Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
#600
Цепочка слов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Будем называть цепочкой слов длины n последовательность слов \(w_1\), \(w_2\), …, \(w_n\), такую, что для всех \(i\) от 1 до \(n\) – 1 слово \(w_i\) является собственным префиксом слова \(w_i\)+1.

Слово \(u\) длины \(k\) называется собственным префиксом слова \(v\) длины \(l\), если \(l\) > \(k\) и первые \(k\) букв слова \(v\) совпадают со словом \(u\). Например, «program» является собственным префиксом слова «programmer».

Задано множество слов \(S\) = {\(s_1\), \(s_2\), …, \(s_m\)} и последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)]. Требуется найти такие числа \(l\) и \(r\) (\(l\) ≤ \(r\)), что \(s_x\)[\(l\)], \(s_x\)[\(l\) + 1], …, \(s_x\)[\(r\) – 1], \(s_x\)[\(r\)] является цепочкой слов, и количество слов в цепочке (число \(r\) – \(l\) + 1) максимально.

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

Первая строка входного файла содержит целое число \(m\) (1 ≤ \(m\) ≤ 250 000). Каждая из следующих \(m\) строк содержит по одному слову из множества \(S\).

Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.

Следующая строка содержит число \(k\) (1 ≤ \(k\) ≤ 250 000). Последняя строка входного файла содержит \(k\) чисел — последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)] (для всех \(i\) выполнено 1 ≤ \(x\)[\(i\)] ≤ \(m\)).

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

Выведите в первой строке выходного файла два числа: \(l\) и \(r\). Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Примеры
Входные данные
3
zngs
rjzr
zng
3
3 1 1
Выходные данные
1 2
Входные данные
6
gjnuitvaowpy
gjnuitvaowpym
gjnuitvaowp
rjzrociinzeco
tgbotnzepnvm
aigqbzpnerv
9
2 3 1 2 3 1 2 3 1
Выходные данные
2 4
#634
Скобки
  
Темы: [Стек]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность из \(N\) круглых, квадратных и фигурных скобок. Выяснить, можно ли добавить в неё цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

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

В первой строке находится число скобок \(N\), во второй - \(N\) символов из набора (, ), [, ], {, }. 1 <= \(N\) <= 100 000.

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

Выводится слово "Yes", если получить правильное арифметическое выражение можно, или "No", если нельзя.

Примеры
Входные данные
2
()
Выходные данные
Yes
Входные данные
6
([{}])
Выходные данные
Yes
Входные данные
6
([{})]
Выходные данные
No
#714
Турнир
  
За победу команда получает 2 очка, за ничью - 1, за поражение - 0. По известным результатам команд требуется восстановить турнирную таблицу.

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.

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

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

В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке  задаются  через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего).

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

Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

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

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

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из \(n\) городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до \(n\), столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог \(T\), вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора \(T\) из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из \(T\) во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

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

В первой строке входного файла записана пара целых чисел \(n\) и \(m\) (\(2 \leq n \leq 4\,000\); \( n - 1 \leq m \leq 100\,000\)), где \(n\) — количество городов в стране, а \(m\)— количество дорог в этой стране. Далее в \(m\) строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел \(a_j\), \(b_j\), \(l_j\), \(t_j\) , где \(a_j\), \(b_j\) это номера городов, соединяемых дорогой (\(1 \leq a_j, b_j \leq n\); \(a_j \neq b_j\)), \(l_j\) — ее длина (\(1 \leq l_j \leq 10^5\)), а \(t_j\) равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор \(T\) удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

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

Выведите \(n - 1\) число в строку через пробелы. \(i\)-ое число должно быть равно либо длине кратчайшго пути из столицы в город \(i + 1\), при условии, что по той дороге из \(T\), которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города \(i + 1\) вообще невозможно.

Примеры
Входные данные
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Выходные данные
6 7 8 5
#745
Хеширование с удалением
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
256 megabytes

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 106.

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

Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из трех символов:    +  означает добавление данной строки в множество;     -  означает удаление  строки из множества;      ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.

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

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

Примеры
Входные данные
+ hello
+ bye
? bye
- bye
? bye
? hello
#
Выходные данные
YES
NO
YES
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест