Задача A. 0 - a, 1 - ab ≡

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

• заменять символ 0 на строку из одного или более символов a
• заменять символ 1 на строку из одного или более символов a, либо на строку из одного или более символов b

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

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

Первая строка входного файла содержит числа N M.

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

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

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

Ограничения

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

3 3
101
bab

Y

4 3
1001
bab

N

Задача B. Переворот бокалов ≡

Условие

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

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

Ограничения

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

7 3

3
1 2 3
3 4 5
3 6 7

Задача C. Неточные подстроки ≡

Условие

Будем говорить, что строки a и b имеют k различий, если длины этих строк одинаковы, а символы в позициях с одинаковыми номерами совпадают все, кроме k штук. Например, строки ABABAC и BBABAB имеют 2 различия.

По данной строке S длиной N символов и числу k требуется найти две подстроки одинаковой длины, начинающиеся с различных позиций, и имеющие не более k различий.

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

Входной файл содержит в первой строке целое число k, в во второй — строку S.

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

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

Ограничения

Строка S состоит из заглавных латинских букв.

0 ≤ k ≤ N ≤ 1000

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

1 
A

0

2
ABCACB

3

Задача D. Круговая оборона ≡

Условие

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

Поскольку содержание армий — дорогостоящее занятие, Централия может постоянно поддерживать только N армий. К счастью, по той же причине её соседи, чья экономика менее стабильна, чем в Централии, могут в i-й год подготовить для завоевания A_i,k армий, где k = 0… 3 — номер соседа.

В Централии проживает могущественный колдун-экономист, который сумел предсказать количество враждебных армий на T лет вперёд. Вам поручена роль главнокомандующего армиями Централии с задачей распределения армий по границам таким образом, чтобы удобный для вторжения случай предоставился как можно позже. Задача осложняется тем, что за один год любая армия Централии может переместиться с той границы, которую она занимала в прошлом году, только на соседнюю границу, т.е. с k-й границы либо на границу (k + 1)mod4, либо на границу (k + 3)mod4.

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

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

В выходном файле должно содержаться число Q — максимальное количество лет, в течение которого можно избежать вторжения (0 ≤ Q ≤ T), за которым следуют Q четвёрок чисел B_i,0 B_i,1 B_i,2 B_i,3 — количество армий, которые следует в i-м году расположить на каждой из границ (B_i,0 + B_i,1 + B_i,2 + B_i,3 = N). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

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

Ограничения

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

4 2
0 4 0 0
2 1 1 0

2
0 4 0 0
2 1 1 0

4 2
0 4 0 0
2 0 1 1

1
0 4 0 0

Задача E. Разрезание прямоугольника ≡

Условие

На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника задано n отрезков, параллельных осям координат.

Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. Размеры получившихся частей должны быть целочисленными. Линия разреза не должна пересекать ни один из заданных отрезков.

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

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

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

Ограничения

1 ≤ h, w ≤ 8

1 ≤ k ≤ h × w

0 ≤ n ≤ 10

0 ≤ X₁ ≤ X₂ ≤ w, 0 ≤ Y₁ ≤ Y₂ ≤ h

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

2 2
4
0

4

8 8
20
0

767625216

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

3