Для строки S определим ее префикс-функцию: \(\pi [i] = max(k|0 \leq k < i; S[1..k] = S[i - k + 1..i])\) для всех \(1 \leq i \leq N\), где \(N\) — длина строки. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1]. Ваша задача по заданной префикс-функции восстановить строку. В качестве символов строки разрешается использование \(M\) первых строчных букв латинского алфавита.

Плоскость разбили на одинаковые прямоугольники размера \(M\times N\) со сторонами, параллельными осям координат, и вершинами, расположенными в точках (\(M\times i, N\times j\)), где \(i\) и \(j\) пробегают всевозможные целые числа. Пусть на этой плоскости задана точка \(P(x,y)\) с целочисленными координатами. Назовем расстоянием от точки \(P\) до некоторого прямоугольника наименьшее из расстояний от \(P\) до точек этого прямоугольника, включая его границу. В частности, расстояние от точки до прямоугольника, в котором она содержится, равно 0.
Требуется написать программу, перечисляющую прямоугольники, удаленные от \(P\) на расстояние, не превосходящее \(L\). Прямоугольники должны быть перечислены в порядке неубывания этого расстояния.

В традиционной музыке используются музыкальные звуки из некоторого набора, именуемого звукорядом. Звуки звукоряда принято группировать в октавы, в каждой из которых 12 звуков. Порядковый номер звука в пределах одной октавы назовем нотой. Таким образом, каждый звук можно задать парой чисел – номером октавы и номером ноты. Номер октавы \(К\) – произвольное целое число, номер ноты \(N\) принимает значение из интервала [01,12]. Звуки можно обозначать этими двумя числами, записанными рядом без пробелов (второе число всегда двузначное). Эту запись назовем кодом \(Q\). Например, \(Q\) = –108 для (–1)-й октавы, восьмой ноты. Значение \(Z\), определяемое по формуле \(Z = K\times 12 + N\) назовем абсолютным номером \(Z\) звука в звукоряде (для приведенного выше примера \(Z = –4\)).
Набор всех звуков, ноты которых принадлежат заданному подмножеству \(P\) номеров нот, назовем гармонией \(G\). Это означает, что любой звук с абсолютным номером \(Z = K\times 12 + n\), где \(n\) – номер ноты из \(P\), принадлежит этой гармонии при любом значении \(K\). Отсюда следует, что гармония однозначно определяется указанием \(P\). Две гармонии назовем эквивалентными, если при прибавлении некоторого одного и того же целого числа ко всем абсолютным номерам звуков первой гармонии получаются все элементы второй гармонии. Ограничимся рассмотрением только таких наборов гармоний, в которые наряду с каждой из гармоний входят и все эквивалентные ей. Для описания набора такого вида достаточно указать из каждой совокупности эквивалентных по одной гармонии \(G_i\) или соответствующему ей подмножеству \(P_i\). Базой \(B\) набора гармоний назовем совокупность всех таких \(P_i\).

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

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

Последовательное звучание произвольных звуков назовем мелодией. Каждому звуку мелодии может быть сопоставлен аккорд в порядке исполнения мелодии. Будем считать мелодию благозвучной для этой последовательности аккордов, если каждый ее звук оказывается в тему для соответствующего ему аккорда. Кучерявостью мелодии назовем сумму модулей разностей абсолютных номеров \(Z\) последовательно исполняемых звуков данной мелодии.

Пусть даны: база \(B\) набора гармоний, последовательность аккордов \(A\) и начальный звук \(Q\). Требуется написать программу, находящую наименее кучерявую из всех благозвучных мелодий, начинающихся с этого звука.

На прямой задано некоторое множество отрезков с целочисленными координатами концов [\(L_i\), \(R_i\)]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, \(M\)], (\(M\) — натуральное число), содержащее наименьшее число отрезков.

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