2010(8 задач)
2011(8 задач)
2012(8 задач)
2013(8 задач)
2014(8 задач)
2015(8 задач)
2016(8 задач)
2017(8 задач)
Московская областная олимпиада(13 задач)
Кировская открытая областная олимпиада(21 задач)
Санкт-Петербург(3 задач)
Строка 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
На окружности отмечено \(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
Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки “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
В театре работает \(n\) актеров. Известно, что среди них \(a\) – высоких, \(b\) – голубоглазых и \(с\) – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.
Требуется написать программу, которая по заданным числам \(n\), \(a\), \(b\) и \(с\) определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.
Первая строка входного файла содержит одно число, которое задает, минимальное или максимальное количество актеров необходимо найти в данном тесте. Это число может принимать следующие значения:
Выходной файл должен содержать одно число – минимальное или максимальное (в зависимости от входных данных) количество актеров, которые могут претендовать на главную роль в новом спектакле.
Правильные решения для тестов, в которых требуется найти минимальное количество актеров, будут оцениваться из 50 баллов.
Правильные решения для тестов, в которых требуется найти максимальное количество актеров, будут оцениваться из 50 баллов.
Несмотря на выделение отдельных групп тестов для минимального и максимального количества артистов, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов из условия задачи.
2 5 3 4 5
3
1 5 3 4 5
2