Задача A. Arithmetic pairs ≡

Условие

Требуется подсчитать общее количество пар целых чисел (p, n) таких, что p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

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

Входной файл содержит два натуральных числа: A и B.

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

Выходной файл должен содержать единственное целое число — количество пар.

Ограничения

2 ≤ A ≤ B < 2⁶³

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

10 100

13

37 48

0

Задача B. Broken chessboard ≡

Условие

Имеется доска размером n × m клеток, в одной из которых расположен шахматный конь. При этом часть клеток предварительно была удалена с доски.

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

Иными словами, заданный список клеток должен являться подпоследовательностью посещённых конём клеток.

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

Входной файл содержит целые числа n и m — размеры доски.

Далее идёт целое число P, за которым следует P пар целых чисел (a_i, b_i) — координаты удалённых клеток.

Далее идёт целое число L, за которым следует L пар целых чисел (x_i, y_i) — координаты клеток, через которые необходимо пройти (включая начальное местоположение коня).

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

Выходной файл должен содержать единственное целое число — минимальное количество ходов.

Если задача не имеет решения, следует вывести −1.

Ограничения

0 < |x_i+1 − x_i| + |y_i+1 − y_i|, 2 ≤ (n, m) ≤ 100,

0 ≤ (a_i, x_i) < n, 0 ≤ (b_i, y_i) < m,

0 ≤ P ≤ 5000, 2 ≤ L ≤ 100

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

5 5

4
2 3
4 3
2 4
1 1

3
3 1
1 2
0 3

5

5 5

4
2 2
4 3
2 4
1 1

3
3 1
2 3
0 3

-1

Задача C. Cut the band ≡

Условие

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

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

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

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

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

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

Вторая строка входного файла содержит N целых чисел a_i — последовательность чисел на ленточке.

Третья строка входного файла содержит целое число M — количество друзей Васи.

Четвертая строка входного файла содержит M целых чисел b_i — нелюбимое число i-го друга. Все b_i различны.

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

Выходной файл должен содержать единственное целое число — минимальное количество разрезов ленточки.

Ограничения

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

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

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0

Задача D. Dissatisfied by spice ≡

Условие

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

Каждому клиенту, в соответствии с его вкусом, требуется определенное количество специй каждого вида. Если же в его блюдо положить недостаточное количество специй, он останется крайне недоволен.

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

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

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

Далее следует целое число N — число клиентов, и матрица P_{i j} — количество специй j-го вида, которые требует i-й клиент. При этом сначала идут все специи для первого клиента, затем для второго и так далее.

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

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

Ограничения

0 < M ≤ 5, 0 < N ≤ 50, 0 ≤ (A_j, P_{i j}) < 10

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

5
6 4 5 7 2

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

3
2
0

5
6 4 5 7 2

4
1 2 3 4 3
7 3 1 0 1
2 1 6 1 2
0 5 0 1 0

Задача E. Equipattern ≡

Условие

Юный дизайнер Вася разрабатывает логотип для своей компании. Он представляет его в виде имени компании, в котором каждая буква покрашена в синий или оранжевый цвет.

Вася хочет раскрасить буквы так, чтобы название состояло из одноцветных подстрок одинаковой длины. Цвета таких подстрок должны чередоваться. То есть если первые X букв покрасить в оранжевый цвет, то следующие X букв нужно красить в синий и т.д.

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

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

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

Первая строка входного файла содержит символы, которые можно красить в синий цвет.

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

Третья строка входного файла содержит строку, которую необходимо покрасить.

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

Выходной файл должен содержать единственное целое число — количество способов покрасить строку.

Ограничения

Все строк состоят из малых латинских букв. Длина строк не превосходит 10⁵.

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

a
b
abc

0

a
b
ab

1

Задача F. Food stalls ≡

Условие

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

Схема представляет из себя строку S, которая состоит из символов '.' — свободное место, 'F' — ларек с едой и 'S' — пост службы безопасности.

Чтобы получить государственное финансирование, план должен соответствовать требованиям Государственной программы Постов и Ларьков к ним. В частности, необходимо предоставить отчет, в котором для i-го поста будет указано два числа l_i и r_i — количество ларьков с едой между данным постом и ближайшим слева постом (либо концом улицы) и количество ларьков между данным постом и ближайшим справа постом (либо концом улицы).

Напишите программу, которая сможет предоставить требуемую отчётность.

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

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

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

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

Ограничения

Длина строки со схемой не превосходит 10⁵.

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

.....FFF.F.F.FS......S..F.

2
6 0
0 1

S

1
0 0

Задача G. Grouping of cells ≡

Условие

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

Изначально таблица была разбита на строки, однако в процессе обработки форматирование потерялось и все разделители (включая переносы строк) оказались заменены пробелами (ASCII 32). При этом известно, что ранее в пределах каждого столбца таблицы числа в ячейках совпадали.

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

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

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

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

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

Ограничения

Значения всех ячеек лежат в диапазоне от 0 до 2³¹ − 1.

Общее число ячеек не превосходит 2 ⋅ 10⁵.

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

10 12 10 12 10 12 10 12 10 12 10 12

1
2
3
6

10 12 10 12 10 12 10 10 10 12 10 12

1

Задача H. Hlelo? wrold ≡

Условие

Юный программист Вася программу "hello world" на простом языке программирования. Программа состоит из одной строки и должна выглядеть так:

print("Hello,World")

Вася очень плохо набирает текст. Пытаясь ввести приведённую выше строку, он нажал клавиши с буквами L раз, клавиши со специальными символами C раз (включая кавычки, запятую и скобки). Вася также нажал клавишу backspace B раз, каждый раз стирая по одному символу.

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

Формат входных данных

Входной файл содержит целые числа L, C, B.

Формат выходных данных

Выходной файл должен содержать единственную строку YES или NO.

Ограничения

0 ≤ L, C, B ≤ 100

L + C ≥ B

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

15 5 0

YES

2 7 6

NO

Задача I. Inner rotation ≡

Условие

Имеются два треугольника, закрепленные в некоторой фиксированной точке F. При этом один из них целиком лежит внутри другого. Каждый треугольник задается вершинами, записанными в полярной система координат (varphi, r) с центром в точке F.

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

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

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

Входной файл содержит 6 вещественных чисел, задающих вершины внешнего треугольника: varphi₁, r₁, varphi₂, r₂, varphi₃, r₃.

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

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

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

Ограничения

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

Оба треугольника являются невырожденными (их вершины не лежат на одной прямой).

Фиксированная точка F является внутренней по отношению к каждому из треугольников.

Все углы varphi_i указаны в радианах и лежат в диапазоне от 0 до 2 ⋅ π.

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

2.10630 2.00000
6.05701 2.00000
4.00000 2.00000

0.00000 0.50000
1.57080 0.50000
3.92699 0.50000

6.28319

2.10630 1.23000
6.05701 1.50000
4.00000 2.00000

6.10430 0.40000
1.57080 0.40000
3.92699 1.60000

0.25326