Задача 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

Problem B2. Karousel ≡

Statement

Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.

There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?

Input format

Two lines of input contain integers n and d.

Output format

Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.

Constraints

1 ≤ (d, n) ≤ 10⁵

Notes on sample

In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.

In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.

Sample tests

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

Problem B5. Discount season ≡

Statement

Vasya has heard that the discount season has started in a shop nearby.

For a single visit to the shop buyer tries to purchase as many items as possible with total weight not greater than W_max, to be able to carry them out with him. There is just one item of every type in the shop. According to discount rules, one client is allowed no more than 3 visits.

You must write a program to calculate optimal sequence of purchases allowing to buy maximum number of items. Total cost of all items must not exceed P_max — the amount of money Vasya has. If several variants with maximum number of items exist, choose one with minimal number of visits.

Input format

Input starts with total number of items n, followed by n pairs of integers: P_i — price of i-th item, W_i — its weight.

Next in the input data are maximum allowed amount of money P_max (total for all visits) and W_max — maximum weight Vasya is able to carry in each visit.

Output format

Output must contain optimal sequence of purchases, described as follows.

First, a total number of visits Vasya has no make. Then for each visit: count of items purchased, followed by item numbers in any order. Items are numbered starting from zero.

If there are several optimal solutions, output any of them.

Constraints

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

Sample tests

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

Problem B7. Kode work? ≡

Statement

A group of students decided to create a startup to replace QR codes with new improved system. They decided to represent binary data as a string of digit patterns for 0 and 1, displayed on a picture below. Picture also contains a representation of a binary string 1001.

Digits in the code are separated by one column of '.' characters, first and last digit are located right on the edges of the code. If the image taken by camera does not exactly coincide with the digit patterns, then the number of differing pixels is called recognition error.

System must determine the minimal recognition error which can be obtained by picking the bit string most closely resembling given image.

Input format

First line of input contains integer n — image width. Following three lines contain the image. Each character is either '#' (ASCII 35), or '.' (ASCII 46).

Output format

Output single integer — minimum possible recognition error.

Constraints

2 ≤ n ≤ 100000

Sample tests

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

0

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

14

Problem B8. Bricks in the wall ≡

Statement

Let's consider a set of n two-dimensional bricks with arbitrary widths W_i and height 1.
It is required to build a wall of width L and maximum possible height (but no greater than 5) using minimum possible count of the bricks.

The bricks are arranged in layers, and each layer should be fully filled, meaning no gaps between bricks are allowed.

One is not allowed turn the bricks. They all should remain a horizontal position.

Input format

The input contains the number n, followed by exactly n integers W_i representing the widths of the bricks.
Next is the number L specifying the width of each layer.

Output format

The output should contain a sequence of brick numbers, arranged in the order of layer formation:
the bricks of the first layer, followed by those of the second layer, and so on.
It is assumed that the bricks are numbered starting from zero.

Constraints

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

Sample tests

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