Комбинаторные алгоритмы : задачник

Министерство образования и науки российской Федерации 

уральский Федеральный университет  
иМени первого президента россии б. н. ельцина

М. о. асанов 
а. л. гальперин 
т. а. сеньчонок

коМбинаторные 
алгоритМы

задачник

рекомендовано методическим советом урФу для студентов, 
обучающихся по программам бакалавриата и специалитета 
по направлениям подготовки 02.03.01 «Математика и компьютерные науки», 
02.03.02 «Фундаментальная информатика и информационные технологии», 
02.03.03 «Математическое обеспечение и администрирование  
информационных систем», 09.03.03 «прикладная информатика»,  
10.05.01 «компьютерная безопасность»

екатеринбург 
издательство уральского университета 
2017

удк 519.254(076.5)
 
а 90

р е ц е н з е н т ы:
отдел математического программирования
института математики и механики им. н. н. красовского уро ран
(заведующий отделом доктор физико-математических наук,  
профессор М. Ю. Хачай);

а. в. келлер, доктор физико-математических наук, доцент
(Южно-уральский государственный университет)

Асанов, М. О.
а 90  
комбинаторные алгоритмы : задачник / М. о. асанов, 
а. л. гальперин, т. а. сеньчонок ; М-во образования и науки рос. 
Федерации, урал. федер. ун-т. — екатеринбург : изд-во урал. ун-та, 
2017. — 80 с. 

ISBN 978-5-7996-2118-6

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

удк 519.254(076.5)

© уральский федеральный университет, 2017
ISBN 978-5-7996-2118-6

Предисловие

предлагаемый задачник по программированию предназначен 
для проведения практических занятий по дисциплине «комбинаторные алгоритмы» на втором и третьем курсах департамента математики, механики и компьютерных наук. цель задачника — формирование у студентов навыков математического моделирования на графах 
для решения задач с использованием оптимизационных алгоритмов.
в задачник включены задачи авторов пособия, а также задачи 
командных и личных соревнований по программированию, проводившихся в уральском государственном, позже федеральном университете с 1997 г. по настоящее время. рядом с номерами некоторых задач 
указаны дополнительные четырехзначные номера в скобках. под 
этими номерами студенты могут найти те же задачи в архиве олимпиадного сервера (http://acm.timus.ru), созданного силами студентов 
и выпускников математико-механического факультета уральского 
государственного университета им. а. М. горького. заинтересованный студент может попробовать свои силы в написании программных решений этих задач, проходящих систему тестов на олимпиадном сервере. в сборнике для таких задач дано описание форматов, 
приведены примеры ввода и вывода, а также указаны фамилия автора 
и название соревнования, на котором эта задача появилась впервые.
задачи структурированы по тематическим разделам в соответствии с рабочей программой дисциплины «комбинаторные алгоритмы». наряду с простыми задачами в каждой теме представлены 
задачи средней и повышенной сложности. для многих задач в специальном разделе приведены решения. за необходимым для решения 
задач теоретическим материалом читатель может обратиться к источникам, указанным в списке рекомендуемой литературы.
задачник по программированию может быть использован как на 
практических занятиях, так и для самостоятельной подготовки студентов к этим занятиям. 

1. ОснОвные ПОнятия,  
жАдные АлгОритМы, ПОиск в грАфе

1.1. куроед

большой любитель курятины по прозвищу карабас барабас 
(далее — кб) купил курицу. курочка снесла ровно 2 яичка, после 
чего кб ее съел. из одного яичка вылупился петушок, из другого —  курочка. петушка кб тут же съел, а курочку съел после 
того, как она принесла 2 яичка. далее кб действовал по такому 
алгоритму. появившихся в каждом поколении петушков съедал 
сразу, а курочек — после того, как они сносили 2 яичка. случилось 
так, что в некотором поколении появились одни петушки, которые 
тут же были съедены, и несчастный кб умер с голоду. оказалось, 
что кб вел строгий учет и в его записях имелась информация, что 
съел он ровно 2 015 петушков. сколько курочек он съел?

1.2. Полтора землекопа (1756)

витя перестукин решает задачу: «три землекопа могут 
вырыть траншею ровно за один день. сколько нужно землекопов, чтобы вырыть такую же траншею ровно за два дня?» у вити 
получилось, что для этого нужно полтора землекопа. но ведь так 
не бывает! на самом деле нужно два землекопа: в первый день 
будет работать только один, а во второй — оба.
известно, что m землекопов могут вырыть траншею ровно 
за d1 дней, если все они будут работать каждый день. помогите 
вите составить график работы землекопов, требующий минимального их числа и позволяющий им выкопать эту траншею 
ровно за d2 дней.

исходные данные

в единственной строке даны три целых числа — m, d1 и d2 
(1 ≤ m; d1, d2 ≤ 10 000).

результат

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

Пример

исходные данные
результат

3 1 2
1 2

Автор задачи: М. асанов.

источник: XI открытое личное первенство ургу (екатеринбург, 13 марта 2010 г.).

1.3. Чудо-дерево

продолжателю дела Мичурина в. пупкину удалось вырастить чудо-дерево, на котором растут бананы и лимоны. к тому 
же дерево обладает невиданными способностями к регенерации. 
если сорвать сразу два банана или два лимона, то мгновенно 
вырастет банан, а если сорвать по одному банану и лимону, то 
вырастет лимон. к несчастью, чудо-дерево выросло рядом со студенческим общежитием, а студенты, как известно, народ вечно 
голодный. однажды, как только на чудо-дереве появились плоды, 
а именно N бананов и M лимонов, каждый проходивший мимо студент считал своим долгом сорвать по два плода. Через некоторое 
время на чудо-дереве висел один-единственный плод. как узнать 
какой именно — лимон или банан?

1.4. любителям футбола

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

1.5. расписания

даны n заявок на проведение занятий. в каждой заявке указано время начала sk и конца fk k-го занятия. все числа целые. 
заявки с номерами k и m считаются совместимыми, если полуинтервалы [sk  fk) [sm fm) не пересекаются. совместимые занятия 
можно проводить в одной и той же аудитории.
рассмотрим следующий алгоритм: на каждом шаге будем 
выбирать занятие с минимальной продолжительностью, совместимое с уже выбранными занятиями. 
1) обеспечит ли этот алгоритм выбор наибольшего числа совместимых занятий?
2) предложите алгоритм сложности O (n) выбора наибольшего числа совместимых друг с другом заявок.
3) предложите эффективный алгоритм составления расписания, использующего минимальное число аудиторий.

1.6. Уникальные отрезки

дан набор из n отрезков, заданных своими концами sk и fk. 
все числа целые. отрезки, не содержащие в себе никакие другие 
отрезки, назовем уникальными.
предложите эффективный алгоритм, определяющий все уникальные отрезки.

1.7. Покрытие единичными отрезками

дано n точек x1, x2, …, xn на координатной прямой; требуется 
покрыть все эти точки наименьшим числом отрезков длиной 1.

1.8. сдача с доллара

требуется набрать сумму в n центов, используя наименьшее 
количество монет.
1) предложите алгоритм, набирающий n центов с помощью 
монет достоинством 25, 10, 5 и 1 цент (именно такие монеты 
используются в сШа).
2) предложите жадный алгоритм, использующий набор из 
монет достоинством с 0, с1, …, с k центов, в котором с 0 > 1, k > 0 
и все числа целые. докажите его оптимальность.
3) приведите набор типов монет, для которого жадный алгоритм не дает оптимального решения.

1.9. выпуклые графы

двудольный граф G = (X, Y, E) называется Y-выпуклым, если 
множество Y можно упорядочить так, что для каждого x из X множество вершин, смежных x, является отрезком.
подмножество А множества X называется Y-доминирующим, 
если каждая вершина y из Y смежна хотя бы одной вершине x 
из А. известно, что задача построения наименьшего по числу вершин Y-доминирующего множества является NP-полной.
предложите эффективный алгоритм построения наименьшего 
Y-доминирующего множества в Y-выпуклом графе.

1.10. Четно-нечетный граф

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

1) предложите алгоритм, который определяет, является ли 
заданный граф четно-нечетным.
2) в случае отрицательного ответа на пункт 1 предложите 
алгоритм, который находит такое максимальное подмножество Х 
вершин графа, что для любых двух вершин i и j из Х выполняется 
следующее условие: все пути между i и j состоят из четного числа 
ребер.

1.11. Шестеренки

N шестеренок пpонумеpованы от 1 до N (N ≤ 10). заданы M 
(0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i, j), 1 ≤ i < j ≤ N 
(шестеpня с номеpом i находится в зацеплении с шестеpней j). как 
узнать, можно ли повеpнуть шестеpню с номеpом 1?

1.12. города

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

1.13. Покраска дверей (1129)

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

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

исходные данные

в первой строке содержится количество помещений в детском 
саду, N ≤ 100. в следующих N строках находится описание дверей 
(в k + 1-й строке — описание дверей k-го помещения). сначала 
в строке указывается количество дверей, потом, через пробел, 
номера помещений, в которые ведут двери из данного помещения 
(номера в строке упорядочены по возрастанию).

результат

выходной файл должен содержать требуемую раскраску 
дверей или слово Impossible, если осуществить такую покраску 
невозможно. в k-й строке должны быть перечислены цвета дверей 
в k-й комнате в том же порядке, что и в исходных данных. зеленый 
цвет обозначается буквой G, оранжевый — Y.

Пример

исходные данные
результат

5
3 2 3 4
3 1 3 5
4 1 2 4 5
3 1 3 5
3 2 3 4

G Y G
Y G Y
G Y Y G
Y G G
G Y Y

Авторы задачи: идея — М. асанов, подготовка — с. васильев.

источник: VI чемпионат уральского государственного университета (екатеринбург, 21 октября 2001 г.).