Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Десятая тренировка

содержание задачника

Задача 10А. Анти-QuickSort

Для сортировки последовательности чисел широко используется быстрая сортировка — QuickSort. Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива. Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Ввод из файла antiqs.in. В первой строке находится единственное число N.
Ограничения: 1 $\le$ N$\le$70 000, время 1 с.
Вывод в файл antiqs.out Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
Пример
Ввод
3
Вывод
1 3 2

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

Строку Фибоначчи F(K) для натуральных чисел К определим так: F(1) = 'A', F(2) = 'В', F(K) = F(K - 1) + F(K -12) при К> 2, где «+» означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов А и В, в строку Фибоначчи F(N). Ограничения: Длина строки S составляет от 1 до 25 символов, 1 $\le$N$\le$ 45, время 1 с. Примечание. Длина F(45) равна 1 134 903 170.
Ввод из файла fibostr.in. В первой строке содержится число N, во второй — строка S.
Вывод в файл fibostr.out. Вывести одно число — количество вхождений строки S в строку Фибоначчи F(N).
Примеры
Ввод
1
A
Вывод
1
Ввод
35
BBABAB
Вывод
1346268

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

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачеркивают ровно К пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет. Ограничения: 1 $\le$ К $\le$ N$\le$ 40, время 10 с.
Ввод из файла crossgam.in. В первой строке содержатся числа М и К, во второй строке — N символов: латинская заглавная O — пустая клетка, латинская заглавная X — зачеркнутая клетка. Вывод в файл crossgam.out. Вывести одно число: 1, если выиграет первый сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.
Примеры
Ввод
4 2
OOOO
Вывод
1
Ввод
5 2
OOOOO
Вывод
2

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

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

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

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

###
###
.##

.#.
.#S
.#.

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

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

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен черно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади — точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.
.***..***
.*.*.**.*
.***.*.**
*...**.*.
На схеме три куска — один без дыр, а два — с одной дырой каждый: первый — площадью 8, второй — площадью 12. Ваша цель — найти кусок с наибольшим количеством дыр в нем. Дыра — это 4-связная область точек, полностью окруженных символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.
Ввод из файла holey.in. В первой строке содержатся два числа W и H, разделенные пробелами. Следующие Н строк содержат по W символов каждая. Символы в этих строках - или * (ASCII 42), или точка (ASCII 46).
Ограничения: 1 $\le$ W, H$\le$100, время 1 с.
Вывод в файл holey.out. Вывести одно целое число — площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.
Пример
Ввод
9 5
.********
.*......*
.*..**..*
.********
Вывод
22

содержание задачника