Задача A. Краткосрочный прогноз ≡

Условие

Вася работает брокером. Его главная задача — предугадывать котировки акций различных компаний, чтобы знать, какие акции надо покупать, а какие продавать. Вася располагает записями котировок акций некоторой компании за предыдущие N дней, и ему нужен прогноз развития ситуации на рынке на следующие K дней. Запись котировок представляет собой последовательность действительных чисел a_i, 1 ≤ i ≤ N. Прогноз должен представлять собой продолжение этой последовательности a_j, N+1 ≤ j ≤ N+K. На прогноз накладываются следующие условия

1. Среднеквадратичное отклонение (СКО) всей полученной последовательности не должно отклоняться от СКО исходных данных более чем на 10⁻³
2. Абсолютная разница между прогнозами за два соседних дня на спрогнозированном участке и при переходе от исходных данных к нему не должна превышать утроенную среднюю абсолютную разницу на исходном участке (|a_j − a_j−1| ≤ 3 M, N+1 ≤ j ≤ N+K)

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

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

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

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

Исходные данные таковы, что хотя бы одно решение всегда существует.

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

Ограничения

2 ≤ N ≤ 4000, 1 ≤ K ≤ N, −10⁹ ≤ a_i ≤ 10⁹

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

4 1
5.01
5.0
5.0
5.0

5

Задача B. Черепаха в лабиринте ≡

Условие

Черепаха Тортила любит исследовать лабиринты: она ползает по лабиринту и считает количество вариантов, которыми можно проползти лабиринт с левого нижнего угла в правый верхний.Тортила умеет ползать только вверх, вправо и влево, и в каждую клетку может вползти только один раз.

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

Вам нужно написать программу для черепахи Тортилы.

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

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

В следующих далее N строчек по M символов содержится описание лабиринта:

• Точка '.'(ASCII 46) обозначает пустую клетку
• Решётка '#'(ASCII 35) обозначает стену, в такие клетки заползти нельзя

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

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

Ограничения

1 ≤ N, M ≤ 500

Гарантируется, что левый нижний и правый верхний углы лабиринта — пустые клетки

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

3 3
...
.#.
...

2

5 3
...
...
#..
.#.
...

6

2 10
........#.
..#.......

0