Задача A. Шушанчики и кроссворд ≡

Условие

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

Схема кроссворда задается прямоугольной таблицей символов шириной W и высотой H. Пустые клетки, в которые следует вписывать буквы, обозначаются символом '#' (ASCII 35). Остальные клетки обозначаются символами '.' (ASCII 46).

Загаданное слово в кроссворде представляется в виде последовательности из трех или более символов '#', идущих подряд слева направо или сверху вниз, ограниченной в начале и в конце либо краями кроссворда, либо символами '.'.

Загаданные слова на схеме не пронумерованы. Вместо этого они упорядочиваются следующим образом. Слова по горизонтали перечисляются перед словами по вертикали. Слова одного направления отсортированы по положению первых букв в кроссворде: сначала по номеру строки (сверху вниз), затем, при равенстве номеров строк, по номеру столбца (слева направо).

Теперь шушачики хотят проверить, правильно ли они решили кроссворд.

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

Формат входного файла

В первой строке входного файла содержатся числа W и H. Следующие H строк по W символов каждая описывают кроссворд.

В (H + 2)-й строке находится число слов N, за которым по одному в строке следуют слова, составляющие предполагаемое решение кроссворда в порядке, соответствующем загаданным словам.

Формат выходного файла

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

Ограничения

3 ≤ W, H ≤ 500, 1 ≤ N ≤ 30000.

Длина любого слова в кроссворде и в его решении — от 3 до 250 символов. Слова состоят только из маленьких латинских букв. Число слов N совпадает с числом загаданных слов в кроссворде.

Примеры тестов

8 7
..#.#...
#######.
..#.#...
..#####.
..#.#...
..#.#...
..#.####
5
program
table
math
contest
problem

CORRECT

8 7
..#.#...
#######.
..#.#...
..#####.
..#.#...
..#.#...
..#.####
5
program
table
math
cantest
problem

cantest

Задача B. Замена скобок: выполнение алгоритма ≡

Условие

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

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и все скобки в ней заменяются на противоположные, т.е. все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

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

Формат входного файла

В первой строке входного файла содержится исходная последовательность.

Во второй строке содержится число N.

В каждой из последующих N строк содержится по два числа l_i r_i, задающих позиции первого и последнего символа подстроки, в которой на i-ом шаге меняются скобки.

Формат выходного файла

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

Ограничения

1 ≤ N, L ≤ 10⁵

1 ≤ l_i ≤ r_i ≤ L

Примеры тестов

(((((
1
1 5 

)))))

((())(()
3
1 8
2 6
4 7

)(((()((

Задача C. Двойные тетради Чебурашки ≡

Условие

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

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

У Чебурашки есть N_S одинарных и N_D двойных тетрадей. Все одинарные тетради имеют вес W_S, а все двойные — вес W_D. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

Формат входного файла

Во входном файле содержатся числа N M N_S N_D W_S W_D. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится K_i — число уроков в i-ый день, за которым следует K_i чисел — номера предметов. Все числа во входном файле целые.

Формат выходного файла

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ W_S, W_D ≤ 10⁹

0 ≤ K₁ + K₂ + …  + K_N ≤ 15

2 × N_D + N_S = M

Примеры тестов

4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4

8

4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4

4

Задача D. Марсианские суеверия ≡

Условие

Недавно стало известно, что все марсиане (как и некоторые люди) боятся чисел 4 и 13. Поэтому в домах на Марсе квартиры и этажи пронумерованы так, что 4-ых и 13-ых квартир и этажей нет. Квартиры и этажи нумеруются подряд начиная с единицы, но после трёх следует пять, а после двенадцати — четырнадцать.

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

Требуется написать программу, которая по данному количеству этажей марсианского дома N и количеству квартир на этаже M определяет, есть ли в нём квартира с номером K и, если есть, выводит номер этажа, на котором она расположена.

Формат входного файла

Во входном файле содержатся числа N M K.

Формат выходного файла

В выходном файле должно содержаться единственное число — номер этажа, на котором находится квартира с номером K, либо  − 1 если такой квартиры в доме нет.

Ограничения

1 ≤ N, M, K ≤ 10⁹

Примеры тестов

7 4 14

3

4 5 21

5

4 5 27

-1

5 7 4

-1

Задача E. Замена скобок: минимизация шагов ≡

Условие

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

• пустая строка является правильной скобочной последовательностью;
• если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.
• если A и B — правильные скобочные последовательности, то AB — тоже правильная скобочная последовательность.

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

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и скобки в ней меняются на противоположные, то есть все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

Требуется написать программу, которая по скобочной последовательности рассчитает минимальное количество шагов N, необходимое для превращения её в правильную.

Формат входного файла

Во входном файле содержится скобочная последовательность.

Формат выходного файла

В выходном файле должно содержаться число N, за которым следуют N пар чисел l_i r_i, задающих позиции первого и последнего символа подстроки, в которой на i-ом шаге меняются скобки. Если существует несколько оптимальных решений, выведите любое из них.

Если решения не существует, выведите единственное число  − 1.

Ограничения

Длина исходной последовательности находится в диапазоне от 1 до 3000 символов

Примеры тестов

()

0

))((()

1
1 4

)((()((()((()(((

2
1 16
2 7

Задача F. Марсианская оптимизация ≡

Условие

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

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

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

Например, для вычисления суммы переменных a b c d e возможны, в частности, следующие варианты вызова функции:

• sum(c,sum(e,sum(a,sum(d,b))))
• sum(b,sum(sum(d,a),sum(c,e)))
• sum(sum(sum(d,e),b),sum(c,a))

В языке Mars# длина имён переменных составляет от одного до восьми символов. Имена переменных состоят из латинских букв.

Формат входного файла

В первой строке входного файла содержится число N. В следующих далее N строках содержатся имена переменных.

Формат выходного файла

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

Аргументы в вызове функции заключаются в круглые скобки '(' (ASCII 40) и ')' (ASCII 41) и разделяются единственным символом ',' (ASCII 44).

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

Ограничения

2 ≤ N ≤ 10⁵

Примеры тестов

5
a
b
z
x
y

sum(z,sum(sum(b,x),sum(y,a)))

6
a
bb
ccc
p
qq
rrr

sum(sum(sum(a,p),sum(bb,qq)),sum(ccc,rrr))

Задача G. Мосты-горки ≡

Условие

Выбор подходящего проекта строительства моста на остров Русский — задача не из лёгких: ведь существует много разновидностей мостов.

В Академии был разработан новый тип мостов — мосты-горки. Эти мосты устанавливаются между двумя островами, один из которых должен быть высоким, а другой низким. Чтобы попасть с высокого острова на низкий, достаточно просто скатиться по мосту, как по горке. При этом даже не нужно тратить топливо! К тому же при достаточной массе автомобиля езда превращается в увлекательный аттракцион.

Но у мостов-горок есть и недостатки:

1. Мост должен быть идеально прямым: массивные автомобили могут не справиться с поворотами на большой скорости.
2. Конструкция мостов-горок такова, что один мост не может проходить над другим мостом, то есть мосты не должны пересекаться друг с другом.

Ввиду заинтересованности правительства в мостах-горках в Академии была организована лаборатория по их исследованию. В лабораторных условиях была создана модель архипелага, в котором N высоких и N низких островов представлены точками на плоскости, причём никакие три острова не лежат на одной прямой. Требуется построить ровно N мостов-горок между островами так, чтобы на каждом острове был мост. Как высокие, так и низкие острова пронумерованы от 1 до N.

Первый пример теста соответствует рисунку справа. Тёмными изображены острова с номером 1, а светлыми — с номером 2. Если соединить тёмные острова со светлыми, то мосты будут пересекаться.

Формат входного файла

Входной содержит число N, за которым следует N пар чисел X_i Y_i — координаты высоких островов, а затем N пар чисел x_i y_i — координаты низких островов.

Формат выходного файла

Выходной файл должен содержать N пар чисел p_i q_i — номера островов, соединённых мостом, где p_i — номер высокого острова, q_i — номер низкого острова. Пары можно выводить в произвольном порядке. Если решений несколько, выведите любое из них.

Если N мостов-горок построить невозможно, то выходной файл должен содержать единственное число  − 1.

Ограничения

1 ≤ N ≤ 1000,  − 10⁵ ≤ X_i, Y_i, x_i, y_i ≤ 10⁵.

Все числа во входном файле целые.

Примеры тестов

2
0 0
1 0
-2 -3
2 -3

1 1
2 2

5
1 0
2 2
-1 0
0 -3
-2 -3
4 -2
2 -2
1 -1
-1 -1
-3 2

1 3
4 1
2 2
5 4
3 5

Задача H. Куб со спицами ≡

Условие

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

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

Формат входного файла

Во входном файле содержится единственное натуральное число N.

Формат выходного файла

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

Ограничения

Примеры тестов

2

1 2
2 1
2 1
1 2