Темы
    Информатика(2656 задач)
---> 109 задач <---
    2009(8 задач)
    2010(8 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(8 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
    Московская областная олимпиада(13 задач)
    Кировская открытая областная олимпиада(21 задач)
    Санкт-Петербург(3 задач)
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.

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

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

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

Система оценки

Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.

Примеры
Входные данные
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
Выходные данные
4
2
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На окружности отмечено \(2n\) различных точек, пронумерованных от 1 до \(2n\) против часовой стрелки. Петя нарисовал \(n\) хорд, \(i\)-я из которых соединяет точки с номерами \(a_i\) и \(b_i\). При этом каждая точка является концом ровно одной хорды.

Теперь Петя заинтересовался, сколько пар хорд пересекаются. Помогите ему определить это количество.

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

Первая строка входных данных содержит целое число \(n\) — количество проведенных хорд (\(1\le n\le 10^5\)). Следующие \(n\) строк содержат по два целых числа — \(a_i\) и \(b_i\).

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

Выведите одно число — количество пар хорд, которые пересекаются.

Примечание

Решения, которые работают только для \(n < 2000\), будут оцениваться из 40 баллов.

Примеры
Входные данные
3
1 4
2 5
3 6
Выходные данные
3
Входные данные
2
1 2
3 4
Выходные данные
0
Входные данные
2
1 4
2 3
Выходные данные
0

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

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

* Если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб.

* Если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

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

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

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

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

Первая строка входного файла содержит целое число \(n\) — количество дубов, растущих на аллее (\(2\le n \le 200\)). Вторая строка содержит \(n\) чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1000.

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

Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число \(-1\).

В случае, если искомый план существует, в первую строку выходного файла выведите целое число \(m\) — минимальное количество дубов, которые необходимо срубить. В следующие \(m\) строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.

Дубы нумеруются слева направо натуральными числами от \(1\) до \(n\).

Если планов с наименьшим числом срубаемых дубов несколько, выведите любой из них.

Система оценки

В 50 баллов оценивается решение для случая, когда все высоты дубов попарно различны.

Примеры
Входные данные
5
3 2 4 8 5
Выходные данные
2
2
4
Входные данные
5
4 5 5 5 6
Выходные данные
0
Входные данные
6
1 1 3 3 2 2
Выходные данные
-1
Входные данные
6
400 300 310 300 310 500
Выходные данные
-1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки “abba” и “madam”.

Для произвольной строки \(s\) введем операцию деления пополам, обозначаемую \(half(s)\). Значение \(half(s)\) определяется следующими правилами:

Если \(s\) не является палиндромом, то значение \(half(s)\) не определено;

Если \(s\) имеет длину 1, то значение \(half(s)\) также не определено;

Если \(s\) является палиндромом четной длины \(2m\), то \(half(s)\) — это строка, состоящая из первых \(m\) символов строки \(s\);

Если \(s\) является палиндромом нечетной длины \(2m+1\), большей \(1\), то \(half(s)\) — это строка, состоящая из первых \(m + 1\) символов строки \(s\).

Например, значения \(half(\mbox{inforamatics})\) и \(half(\mbox{i})\) не определены, \(half(\mbox{abba}) = \mbox{ab}\), \(half(\mbox{madam}) = \mbox{mad}\).

Палиндромностью строки \(s\) будем называть максимальное число раз, которое можно применить к строке \(s\) операцию деления пополам, чтобы результат был определен.

Например, палиндромность строк “informatics” и “i” равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк “abba” и “madam” равна 1, а палиндромность строки “totottotot” равна 3, поскольку операция деления пополам применима к ней три раза: “totottotot” → “totot” → “tot” → “to”.

Рассмотрим все строки длины \(n\), состоящие из строчных латинских букв, палиндромность которых равна \(p\). Ваша задача — найти \(k\)-ю в алфавитном порядке среди этих строк.

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

В первой строке входного файла содержатся три целых числа \(n\), \(p\) и \(k\) — длина и палиндромность строк рассматриваемого множества и номер искомой строки в этом множестве (\(1 \le n \le 200\); \(0 \le p \le 8\); \(1 \le k \le 10^9\)).

Гарантируется, что в множестве строк длины \(n\) с палиндромностью \(p\) содержится не менее \(k\) элементов, то есть искомая строка существует.

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

В выходной файл выведите \(k\)-ю в алфавитном порядке строку из множества строк длины \(n\) с палиндромностью \(p\).

Примеры
Входные данные
4 1 1
Выходные данные
abba
Входные данные
10 3 490
Выходные данные
totottotot
Входные данные
5 0 6597777
Выходные данные
olymp
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В театре работает \(n\) актеров. Известно, что среди них \(a\) – высоких, \(b\) – голубоглазых и \(с\) – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам \(n\), \(a\), \(b\) и \(с\) определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

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

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

  • 1, если в данном теcте требуется определить минимальное количество актеров;
  • 2, если в данном тесте требуется определить максимальное количество актеров.
Вторая строка входного файла содержит разделенные пробелами четыре целых числа: \(n\), \(a\), \(b\), \(с\) (\(1 \leq n \leq 10 000\), \(0 \leq a \leq n\), \(0 \leq b \leq n\), \(0 \leq c \leq n\)).
Выходные данные

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

Система оценивания

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

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

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

Примеры
Входные данные
2
5 3 4 5
Выходные данные
3
Входные данные
1
5 3 4 5
Выходные данные
2

Страница: << 11 12 13 14 15 16 17 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест