«Базовые структуры данных и алгоритмы языка Python на примере задач информатики повышенного уровня»

Куракин П. В.

Институт проблем управления им. В. А. Трапезникова РАН

МФТИ - «Потенциал»

I. Некоторые общие методы и подходы

Внимание. Эти темы и сопутствующие им задачи (они типовые) предполагаются обязательной и неизменной частью курса.

1. Рекурсия. Числа Фиббоначи. Простейший вариант рекурсии. Мемоизация. Автоматическая мемоизация. Задача о Ханойской башне. Начала динамического программирования. Задача о воришке. Задача о размене монет.

2. Задачи поиска. Поиск подстроки в строке на примере ДНК. Хранение ДНК – строки. Линейный поиск. Бинарный поиск. Задачи на прохождение лабиринта. Создание лабиринта. Мелкие детали лабиринта. Поиск в глубину. Поиск в ширину. Задача «Миссионеры и людоеда».

3. Задачи с ограничениями (CSP = constraint satisfaction problems). Разработка общего инструментария (framework) решения CSP – задач. Задача о раскраске карты Австралии. Задача о восьми ферзях. Задача о размещении электронных компнентов на печатной плате.

4. Задачи теории графов. Поиск кратчайшего пути в графе. Алгоритм Дейкстры. Поиск минимального связующего дерева.           

II. Некоторые выделенные задачи.

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

1. Попытка к бегству. Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. Требуется найти количество различных маршрутов, ведущих к спасению.

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

3. Расписание. На конференции работников народного образования с докладами об очередном улучшении финансирования желает выступить несколько министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.

4. Рациональные дроби. Даны две положительные рациональные дроби: a/b и c/d. Найдите их сумму и запишите ответ в виде несократимой дроби.

5. Прямоугольники. Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на какое количество частей эти прямоугольники разбивают плоскость.

6. Ферзя в угол. В левом нижнем углу доски M×N стоит ферзь. Двое игроков по очереди ходят ферзем, перемещая его на любое число клеток по вертикали вверх, по горизонтали вправо, или по диагонали вправо-вверх. Выигрывает тот, кто поставит ферзя в правый верхний угол доски. Определите, какой из игроков имеет выигрышную стратегию.

7. Удаление клеток. Из прямоугольного листа бумаги (M строк, N столбцов) удалили некоторые клетки. Определите, на сколько кусков распадается оставшаяся часть листа. Две клетки не распадаются, если они имеют общую сторону.

8. Морской бой. На прямоугольном поле для игры в морской бой размером M×N расположено несколько прямоугольных кораблей. Корабли не соприкасаются друг с другом. Ваша задача — определить всевозможные типы кораблей на поле и число кораблей каждого типа. Два корабля относятся к одному типу, если их размеры совпадают (корабли, которые могут быть получены друг из друга поворотом, также относятся к одному типу).

9. Шестеренки. На плоскости расположена система из N одинаковых шестеренок, которая приводится в движение вращением шестеренки 1 по часовой стрелке (`clockwise'). Требуется определить направление вращения каждой шестеренки системы, либо установить, что систему заклинит.

10. Красильщик. У красильщика имеется N предметов, которые он должен покрасить. Красильщик красит i-й предмет за время p_i, после чего предмет сохнет время q_i. Одновременно красильщик может красить только один предмет, а сохнуть одновременно может произвольное число предметов. Определите последовательность, в которой красильщик должен красить предметы, чтобы сделать суммарное время выполнения работы минимальным (время считается от начала работы до того момента, когда высохнут все предметы).

11. Вложенные ящики. Рассматриваются n-мерные ящики, заданные длинами своих сторон (двумерный ящик – это прямоугольник, трехмерный - параллелепипед). Необходимо проанализировать свойства группы таких ящиков. Надо найти в данной группе ящиков такую последовательность максимальной длины, что каждый следующий ящик можно «вложить» в предыдущий.

12. Десант. Отряд из  m (1 <= m <= 10) десантных кораблей прорывается к берегу прорывается к берегу через минное поле. План минного поля известен. Опасные места обозначены четырехугольниками. Обходить по контуру эти четырехугольники можно, а внутрь заходить нельзя. Всего имеется n (1 <= n <= 20) непересекающихся четырехугольников. Место высадки десанта для каждого корабля строго определнно. Требуется найти для десантных кораблей такие маршруты, чтобы сумма расстояний, пройденная всем кораблями была минимальной.