Задача B1. Лягушка-попрыгун ≡

Условие

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

Сама лягушка может прыгать только одним из следующих способов:

1. Прыгнуть на 2 клетки вверх

2. Прыгнуть на 2 клетки вправо

3. Прыгнуть на 1 клетку по-диагонали

Лягушка не может выходить за границы сетки

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

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

Входные данные состоят из двух чисел, записанных через пробел: N и M

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

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

Ограничения

2 ≤ N ≤ 10³

2 ≤ M ≤ 10³

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

3 3

3

5 2

0

4 4

7

Задача B2. Karousel ≡

Условие

В детском парке открылся новый аттракцион "Карусель" на n мест. Согласно технике безопасности при её эксплуатации рассаживать детей можно только таким образом, чтобы центр тяжести всех катающихся совпадал с центром карусели и расстояния между ними по окружности были одинаковыми. Например, при n = 6 одновременно могут кататься 2, 3 или 6 ребят, а при n = 5 — только ровно 5. Другими словами, разрешается запустить карусель, если на ней размещено k детей, причём k — делитель n и k ≠ 1.

В очереди к карусели стоит d детей. Дети, которые покатались на карусели, уходят в поисках новых развлечений. Какое минимальное количество запусков аттракциона следует осуществить, чтобы все дети прокатились на карусели ровно по одному разу?

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

Две строки входных данных содержат натуральные числа n и d.

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

Выведите одно натуральное число — ответ к задаче. Если всех ребят прокатить не получится, выведите -1.

Ограничения

1 ≤ (d, n) ≤ 10⁵

Пояснение к примеру

В первом примере дано n = 16 и d = 14 (карусель на 16 мест, в очереди 14 детей). Достаточно 3 запуска карусели: в первый раз прокатятся 8 ребят, во второй — 4, в третий — 2.

Во втором примере дано n = 15 и d = 7. Всех детей прокатить не получится, так как согласно правилам разрешено катать только по 3, 5 или 15 ребят.

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

16
14

3

15
7

-1

Задача B3. Наибольшая возрастающая подпоследовательность ≡

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

Задача B4. Свинья-копилка ≡

Условие

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

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

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

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

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

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

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1

Задача B5. Discount season ≡

Условие

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

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

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

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

В начале входных данных указано общее количество товаров n, за которым следует n пар целых чисел: P_i — стоимость i-го товара, W_i — его вес.

Далее во входных данных следует максимальная допустимая стоимость P_max (в сумме за все заходы) и вес W_max, который может унести Вася за один заход.

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

Выходные данные должны содержать оптимальную последовательность покупок, записанную в следующем виде.

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

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

Ограничения

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

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

12

10 2
10 2
10 8
10 2
5 3
10 2
1 7
10 2
10 4
10 2
1 3
10 2

100 10

3
3 9 10 11
5 0 1 3 5 7
2 4 6

10

4 1
5 2
1 3
8 2
7 1
5 2
8 3
7 1
5 1
6 8

24 8

1
5 0 1 2 4 8

Задача B6. Домино (классика) ≡

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

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

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

2 3

3

Задача B7. Kode work? ≡

Условие

Группа студентов решила создать стартап для замены QR-кодов на новую улучшенную систему. Они решили представлять двоичные данные как строку из шаблонов цифр 0 и 1. Также на рисунке изображено представление двоичной строки 1001.

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

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

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

Входные данные содержат в первой строке одно целое число n — ширину изображения. В следующих трёх строках расположено само изображение. Каждый его символ равен либо '#' (ASCII 35), либо символ '.' (ASCII 46).

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

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

Ограничения

2 ≤ n ≤ 100000

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

5
.#..#
##.##
.#..#

0

14
.#.#.#.##.#..#
##.#.#.##.#.##
.#####.####..#

14

Задача B8. Bricks in the wall ≡

Условие

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

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

Переворачивать кирпичи нельзя — все они должны сохранять горизонтальное положение.

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

Во входных данных указано число n, за которым следует ровно n целых чисел W_i.
Далее записано число L, задающее ширину слоя.

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

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

Ограничения

0 < W_i ≤ L ≤ 20, 0 < n ≤ 100

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

8
1 2 5 1 4 1 3 1
5

4 7 1 6 2

7
1 2 5 5 2 3 3
6

5 6 0 3

6
1 1 1 1 1 1
7

Задача C1. Дерево ≡

Условие

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

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача C2. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

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

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

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

Problem C3. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача C4. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача C5. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

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

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

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

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

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

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

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

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

Ограничения

1 ≤ n, m ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO