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

Условие

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

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

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

В первой строке входного файла содержатся числа 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

Задача B. Коридор ≡

Условие

Коридор размером N на M решили застелить покрытием, представляющим собой плитки размером 1 на M. Сколькими способами можно это сделать, если не должно быть не застеленной поверхности?

Для коридора с размерами N = 6 и M = 4, существуют 4 способа укладки плиток.

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

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

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

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

Ограничения

2 ≤ N, M ≤ 50

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

4 2

5

7 3

9

6 4

4

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

Условие

Лягушка попала в пруд с кувшинками, который можно представить в виде сетки 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

Задача D. Компьютерное зрение ≡

Условие

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

Камера робота позволяет записывать черно-белые прямоугольные изображения шириной c и высотой r ячеек. Черная ячейка на изображении кодируется символом '#', а белая символом '@'. Ромбом называется связная область изображения, целиком состоящая из черных ячеек и удовлетворяющая следующим критериям:

• Ромб имеет какую-то целую высоту h ≥ 0.
• Ромб имеет центр, описываемый двумя координатами 1 ≤ x_c ≤ c, 1 ≤ y_c ≤ r. (x_c, y_c) — позиция ячейки на изображении.
• Все ячейки, имеющие координаты x, y, такие что |x−x_c| + |y−y_c| < h принадлежат ромбу и обязаны иметь черный цвет.

Например, вот корректные изображения ромбов имеющих высоту 2 (обратите внимание, что к ромбу могут прилегать и другие черные ячейки):

@@#@@ @###@ #####

@###@ ##### #####

@@#@@ @@#@@ #####

@@#@@ @###@ @@@@@

@#@#@ @@### @@@@@

@@#@@ @@#@@ @@@@@

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

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

В первой строке находятся два натуральных числа 1 ≤ r, c ≤ 1000 — высота и ширина изображения.

В следующих r строках находятся по c символов '@' или '#', означающих цвет ячеек изображения. '@' - белый цвет, '#' — черный цвет.

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

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

Ограничения

1 ≤ r, c ≤ 10 — 40 баллов

1 ≤ r, c ≤ 100 — 20 баллов

1 ≤ r, c ≤ 1000 — 40 баллов

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

5 5
@@#@@
@###@
#####
@###@
@@#@@

3

3 5
@#@#@
#####
@#@#@

2

3 3
@@@
@@@
@@@

0

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

Условие

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

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5