SnarkNews summer series - 2007, round 2


Объём памяти, предоставляемый программе, составляет 64 Mb.

        Задача A. Деление длинного числа на короткое

Даны целое неотрицательное число M и целое положительное число N. Найти M div N и M mod N.
Ограничения: 0 <= M <= 1060 000, 1 <= N <= 1 000 000, время 2 с.
Ввод из файла divshort.in. В первой строке находится число M, во второй - N.
Вывод в файл divshort.out. В первой строке вывести значение выражения M div N во второй - выражения M mod N.
Примеры 
Ввод 1
12345678901234567890
1000
Вывод 1
12345678901234567
890

        Задача B. Строки Фибоначчи

Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов Aи B, в строку Фибоначчи F(N).
Ограничения: длина S от 1 до 25, 1 <= N <= 45, время 2 с.
Примечание. Длина F(45) равна 1 134 903 170.
Ввод из файла fibostr.in. В первой строке содержится число N, во второй - строка S.
Вывод в файл fibostr.out. Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).
Примеры 
Ввод 1 Ввод 2 Ввод 3 Ввод 4
1         2         8          35
A         ABA       BBABAB     BBABAB
Вывод 1 Вывод 2 Вывод 3 Вывод 4
1         0         3          1346268

        Задача C. Игра в зачёркивание

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.
Ограничения: 1 <= K <= N <= 40, время 2 с.
Ввод из файла crossgam.in. В первой строке содержатся числа N и K, во второй строке N символов: латинская заглавная O- пустая клетка, латинская заглавная X- зачёркнутая клетка.
Вывод в файл crossgam.out. Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.
Примеры 
Ввод 1 Ввод 2 Ввод 3
4 2       5 2       7 2
OOOO      OOOOO     OXXOXXO
Вывод 1 Вывод 2 Вывод 3
1         2         0

        Задача D. Граница многоугольника

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000, время 2 с.
Ввод из файла border.in. В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод в файл border.out. Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.
Примеры 
Ввод 1
3
10 0
0 10
0 0
Вывод 1
30

        Задача E. Путь спелеолога

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N 3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.
Ограничения: 1 <= N <= 30, время 2 с.
Ввод из файла speleo.in. В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: #- обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.
Вывод в файл speleo.out. Вывести одно число - длину пути до поверхности.
Примеры 
Ввод 1
3

###
###
.##

.#.
.#S
.#.

###
...
###
Вывод 1
6
Комментарий 1
Нужно спуститься на уровень вниз,
сделать два движения на запад,
подняться на уровень вверх,
сделать движение на юг,
подняться на уровень вверх.

        Задача F. Дырявая ткань

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади - точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали. 
.***..***
.*.*.**.*
.***.*.**
*...**.*.
На схеме три куска - один без дыр, а два - с одной дырой каждый: первый площадью 8, второй - площадью 12.

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

Ввод из файла holey.in. В первой строке содержатся два числа W и H, разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках - или *(ASCII 42), или точка (ASCII 46).

Ограничения: 1 <= W, H <= 100, время 2 с.

Вывод в файл holey.out. Вывести одно целое число - площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.

Примеры 
Ввод 1
9 5
.********
.*......*
.*..**..*
.*......*
.********
Вывод 1
22