Жадные алгоритмы. Динамическое программирование. Лабораторная работа № 6

1.

Лабораторная
работа №6
ассистент кафедры ИТиСУ
Павлов Марк Владимирович
pavlov.mark@urfu.ru

2.

Общие вводные
В данной работе мы решим задачи на две темы сразу
- жадные алгоритмы (2 – 3 шт)
- динамическое программирование (2 – 3 шт)
18
19
21
2

3.

Задача 2. Маршрутка
Водитель маршрутки Сергей Александрович Жадных прославился своей феноменальной
жадностью повсеместно. Он сам неоднократно заявлял, что за лишнюю копейку готов задушить
родного брата и продать всех друзей. К сожалению, проверить эти слова не представлялось
возможным, поскольку никакого брата, а также друзей, дома и семьи у Сергея Александровича не
было. И что ещё хуже, денег у него тоже не было. Единственным достоянием г-на Жадных
являлась старая маршрутка, на которой он и колесил по городу, подвозя редких пассажиров и
время от времени осматривая краем глаза тротуары в поисках мелких монет...
В один из дней небеса сжалились на Сергеем Александровичем и решили прекратить его
бесполезное существование в этом жестоком мире. С сей благой целью на голову ничего не
подозревавшего г-на Жадных, вышедшего из маршрутки на призывный блеск 5-рублёвой монеты,
свалился топор. Мечты о выгодной продаже бутылки мигом вылетели у него из головы, поскольку
их место занял топор. В переносном смысле этого слова. Орудие небес не смогло пробить
окостеневший череп г-на Жадных, однако, как выяснилось позднее, придало ему несколько
весьма полезных свойств.
3

4.

Задача 2. Маршрутка
Вскоре после продажи топора Сергей Александрович обнаружил, что способен предвидеть
будущее. Какие возможности, какие перспективы открылись незадачливому водителю маршрутки!
Кто мы такие и куда идём? Чего бояться и на что надеяться? Ответы на эти вопросы г-на Жадных
совершенно не интересовали. А вот на то, чтобы с помощью новых умений попытаться заработать
немного денег, выполняя привычную работу, сообразительности у Сергея Александровича
хватило.
4

5.

Задача 2. Маршрутка
Ежедневно маршрутка совершает один рейс от первой до N-й остановки. В маршрутке M мест
для пассажиров. Вечером, просчитав линии вероятностей, г-н Жадных (между прочим,
потенциальный Тёмный Иной шестого уровня) выяснил, что завтра на остановках маршрутку будут
поджидать K человек. Для каждого человека были определены номер остановки S[i], на которой
он желает сесть в маршрутку, и номер остановки F[i], на которой он собирается выйти. В
соответствии с ценовой политикой Сергея Александровича, каждый пассажир должен заплатить P
рублей за билет независимо от количества остановок. Более того, притормозив на остановке, г-н
Жадных может выбирать, кого из желающих посадить в маршрутку, а кого нет. Ставя перед собой
задачу максимизации прибыли, Сергей Александрович вполне разумно решил определить, каких
именно людей нужно сажать в маршрутку. К сожалению, для этого его сил оказалось
недостаточно. А Ваших?
5

6.

Задача 2. Маршрутка
Входные данные
Первая строка содержит целые числа N (2 ≤ N ≤ 100000), M (1 ≤ M ≤ 1000), K (0 ≤ K≤ 50000) и P
(1 ≤ P ≤ 10000). Каждая из следующих K строк содержит целые числа S[i] и F[i] (1 ≤ S[i] < F[i] ≤ N) для
соответствующего человека.
Выходные данные
В первую строку вывести максимальную прибыль. Во вторую строку вывести через
пробел и в любом порядке номера людей, которых следует сажать в маршрутку для
получения этой прибыли. Если задача имеет несколько решений, то вывести любое из них.
6269
14
26
15
23
46
36
36
1564
6

7.

Задача 2. Маршрутка
1.
2.
3.
4.
План решения
Необходимо обеспечить порядок пассажиров так, чтобы их можно было взять как можно
больше => берем пассажиров так, что они раньше выходили, а значит можно было взять их как
можно больше (жадный подход)
Для поддержки пассажиров, которые находятся в маршрутке будем использовать мин-кучу
При просмотре каждого пассажира будет рассматривать остановку, на которой он зашел,
остановку, на которой он выходит, а также его порядковый номер
1. Проверяем маршрутку, вышли ли пассажиры (их F меньше или равен текущему S)
2. Если места освободились, то добавим текущего пассажира (его F), а также запомним его
номер, так как он входит в итоговую выборку
Посчитаем доход маршрутки и выведем все выбранных пассажиров
7

8.

Задача 3. Танец точек
На прямой располагается 1 ≤ N ≤ 10000 точек с целочисленными координатами –
109 ≤ Vi ≤ 109. Каждой из точек разрешается сделать ровно одно движение
(танцевальное па) в любом направлении на расстояние не больше 0 ≤ L ≤ 108 и
остановиться на другой позиции.
Какое минимальное количество точек может остаться на прямой после окончания
танца (все точки после танца, оказывающиеся на одной позиции, сливаются в
одну)?
Формат входных данных:
LN
V1 V2 … VN
Формат выходных данных:
MinimalNumberOfPoints
8

9.

Задача 3. Танец точек
1.
2.
3.
4.
План решения
Сортировка точек по возрастанию
Необходимо поддерживать центры отрезков, куда будут входить наши точки
1. Начальный центр center = v[0] + L
Изначально будем считать, что все точки сходятся в одну точку
Для всех оставшихся, кроме первой, точек:
1. Проверяем, не входит ли она в текущий отрезок (v[i] – L > center)
2. Если не входит, то инкрементируем число отрезков, обновляем центр
9

10.

Задача 8. Интересная игра c числами
Рассмотрим следующую интересную игру для двух игроков. Для этой игры необходима таблица из 2-х
строк и N столбцов, в клетках которой записаны натуральные числа, следующего вида:
A1
B1
A2
B2
A3
B3
...
...
AN
BN
Игроки делают ходы по очереди. Начинает игру 1-й игрок. За один ход 1-й игрок выполняет следующие
два действия:
• выбирает произвольный столбец (к примеру, j-й), который еще ни разу не был выбран одним из
игроков на предыдущих ходах;
• прибавляет к своим очкам число Aj.
За один ход 2-й игрок выполняет следующие два действия:
• выбирает произвольный столбец (к примеру, j-й), который еще ни разу не был выбран одним из
игроков на предыдущих ходах;
• прибавляет к своим очкам число Bj.
10

11.

Задача 8. Интересная игра c числами
Игра заканчивается, когда какой-либо из игроков не сможет сделать ход (по той
причине, что все столбцы уже были выбраны).
Изначально, у каждого из игроков есть 0 очков.
После того, как игра закончилась, происходит взаиморасчет между игроками. К
примеру, 1-й игрок набрал S1 очков, а 2-й игрок - S2 очков.
В случае, когда S1 > S2, 2-й игрок отдает 1-му игроку S1-S2 УДЕ (условных
денежных единиц).
В противном случае, 1-й игрок отдает 2-му игроку S2-S1 УДЕ.
С этих позиций, целью 1-го игрока является максимизация величины S1-S2, а
целью 2-го игрока - максимизация S2-S1.
Назовем стоимостью игры величину S1-S2 при оптимальной игре обоих игроков.
Напишите программу, которая определяет стоимость игры.
11

12.

Задача 8. Интересная игра c числами
1 1
11
1
2 2
11
11
0
3 3
12
34
56
2
12

13.

Задача 8. Интересная игра c числами
План решения
1. Сортируем по убыванию сумму столбца (a[i] + b[i])
2. Подсчитываем суммы очков по каждому игроку (первый возьмет все
четные столбцы, а второй – нечетные
3. Разность сумм – искомое значение
13

14.

Задача 9. Индикаторы
Недавно
Вася
приобрел
настольный
калькулятор
с
жидкокристаллическим индикатором. Этот индикатор отображает N цифр с
помощью N одинаковых элементов.
Отметим, что каждый элемент содержит семь полосок, каждая из которых может
быть либо белой, либо черной. В частности, при отображении цифры «1» черными
являются две полоски.
Вася – очень любознательный мальчик, поэтому он хочет узнать, какое
максимальное и минимальное N-значное число могут быть отображены на
индикаторе его нового калькулятора так, чтобы черными были ровно K полосок.
Напишите программу, которая найдет ответ на Васин вопрос. Учитывайте при этом,
что числа не могут содержать ведущие нули.
14

15.

Задача 9. Индикаторы
segments = { Формат входных данных:
0: 6,
Входной файл INPUT.TXT содержит два натуральных числа N и K (1 ≤ N ≤
1: 2,
100, 1 ≤ K ≤ 700).
2: 5,
Формат выходных данных:
3: 5,
В первой строке выходного файла OUTPUT.TXT выведите минимальное
4: 4,
число, во второй строке выходного файла выведите максимальное число.
5: 5,
6: 6,
Если указанным образом не может быть представлено ни одно число,
7: 3,
выходной файл должен содержать одну строку NO SOLUTION.
8: 7,
9: 6
}
15

16.

Задача 9. Индикаторы
План решения
1. Для минимального числа
1. На каждой позиции нужно выбирать самую маленькую цифру ( 1 – для первой цифры, 0
– для последующих) жадный подход
2. После выбора цифры нужно убедится, что количество оставшихся сегментов достаточно
для построения числа длины n: 2 * (n - i) <= s <= 7 * (n - i) (двойка из двух сегментов,
девятка из 7 сегментов)
3. На последней позиции нужно проверить, что задействованы все сегменты
2. Для максимального числа
1. На каждой позиции нужно выбирать самую большую цифру, начиная с 9
2. После выбора цифры нужно убедится, что количество оставшихся сегментов достаточно
для построения числа длины n: 2 * (n - i) <= s <= 7 * (n - i) (двойка из двух сегментов,
девятка из 7 сегментов)
3. На последней позиции нужно проверить, что задействованы все сегменты
16

17.

Задача 9. Индикаторы
План решения
1. Для каждого позиции
1. Храним флаг, нашли ли число
2. Делаем берем по цифрам:
1. Получить количество сегментов у цифры
2. Если эту цифру не можешь взять, то пропускаем
3. Иначе будем считать, что мы ее взяли, но сначала выполним проверки
4. Запоминаем, сколько останется сегментов, если взять эту цифру
5. Запоминаем, сколько еще позиций остается
6. Если собрали нужное количество цифр, то
1. Если выбрали все сегменты
1. Берем эту цифру в число
2. Обновляем количество оставшихся сегментов
3. Помечаем, что число выбрано и выходим из цикла
2. Иначе пропускаем, не беря эту цифру
7. Иначе проверим условие 2 * (n - i) <= s <= 7 * (n - i)
1. Берем цифру, если выполняется, иначе пропускаем цифру
3. Если так и не нашли подходящую цифру, то возвращаем None
2. Возвращаем число, если набрали нужное количество сегментов, иначе None
17

18.

Задача 10. Коррозия металла
Для хранения двух агрессивных жидкостей A и B используется емкость с
многослойной перегородкой, которая изготавливается из имеющихся N листов.
Для каждого листа i (i = 1, …, N) известно время его растворения жидкостью A — ai
и жидкостью B — bi. Растворение перегородки каждой из жидкостей происходит
последовательно лист за листом, с постоянной скоростью по толщине листа.
Требуется написать программу проектирования такой перегородки, время
растворения которой было бы максимальным.
18

19.

Задача 10. Коррозия металла
Формат входных данных:
В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 256). В
каждой из последующих N строк содержатся два положительных вещественных
числа ai и bi, разделенные пробелом (числа не превышают 106 и состоят не более
чем из 11 значащих цифр).
Формат выходных данных:
В первую строку выходного файла OUTPUT.TXT записать время растворения
перегородки с точностью, не меньшей 10-3. В следующую строку файла записать
номера листов в порядке их расположения от жидкости A к жидкости B, разделяя
числа пробелами.
19

20.

Задача 10. Коррозия металла
План решения
1. Сортировка перегородок (их лучше представить в виде класса) по убыванию
отношения a/b, а также по номеру, чтобы получались корректные ответы для
тестов)
2. Подсчет времени, сколько они продержатся:
1. Будем убирать последовательно перегородки слева и справа, в зависимости
от их скоростей разъедания
1. Если левая перегородка растворяется быстрее (за время dt):
1. Добавляем время (dt) к итоговому
2. Пересчет, на сколько правая перегородка растворилась за dt
1. Для жидкости А (пропорция): right.a * ((right.b – left.a) / right.b)
2. Для жидкости B (разность): right.b – left.a
3. Переход к следующей левой перегородке
20

21.

Задача 10. Коррозия металла
План решения
2.1.2 Иначе:
1. Добавляем время растворения правой (dt) к итоговому
2. Аналогичный пересчет уже для левой перегородки по правой
3. Переход к следующей правой
2.2. Проверка на одновременное растворение:
1. Если значение левой перегородки <= 0, то переходим к следующей
2. Если значение правой перегородки <=0, то переходим к следующей
3. Проверка, если осталась одна перегородка, то она растворяется с двух
сторон:
1. время растворения равно отношению произведения временем на их
сумму
21

22.

Задача 11. Расстояние по Левенштейну
Расстоянием Левенштейна между двумя строками s и t называется количество
атомарных изменений, с помощью которых можно одну строку превратить в другую.
Под атомарными изменениями подразумеваются: удаление одного символа, вставка
одного символа, замена одного символа на другой.
Найди расстояние Левенштейна для предложенной пары строк.
Выведите единственное число – расстояние между строками.
Формат ввода данных:
В первой строке дана строка s, во второй – строка t. Длины обеих строк не
превосходит 1000. Строки состоят из маленьких латинских букв
Подробнее:
https://habr.com/ru/articles/676858/
22

23.

Задача 11. Расстояние по Левенштейну
1.
2.
3.
4.
План решения
Создаем матрицу L*N, где L и N – длины строк
Обрабатываем базовые случаи: i-ая строка для удаления символов из первой
строки, j-столбец для вставки символов в первую строку
Заполнение матрицы:
1. Если символы совпадают, то dp[i][j] = dp[i-1][j-1]
2. Иначе выбираем минимум из трех условий:
1. Удаление (dp[i-1][j] + 1)
2. Вставка (dp[i][j-1] + 1)
3. Замена (dp[i-1][j-1] + 1)
Ответ забираем из правого нижнего угла
23

24.

Задача 12. Одинаковые суммы
1.
2.
3.
4.
5.
6.
План решения
Подсчитываем общую сумму очков
Если общая сумма нечётная, разделить её на две равные части невозможно
Вычисляем половину общей суммы
Инициализируем массив dp
1. dp[x_sum] истинно, если можно получить из элементов массива сумму x_sum
2. dp[0] - истинно по умолчанию, остальные до half_sum – False
Заполнение массива
1. Для каждого элемента массива перебираем возможные суммы от полусуммы
до 0, проверяя
1. Можно ли получить текущую сумму с этим элементом или без него
2. Если уже получили полусумму (текущая сумма равна полусумме),
1. досрочно выходим
Возвращаем dp[-1]
24

25.

Задача 18. Одинаковые суммы
Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число
правильным, если его K-ичная запись не содержит двух подряд идущих нулей.
Например:
1010230 — правильное 7-значное число;
1000198 не является правильным числом;
0001235 — не 7-значное, а 4-значное число.
Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N
цифр.
Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные переводом строки.
Формат выходных данных
Искомое количество в десятичной записи.
25

26.

Задача 18. Одинаковые суммы
План решения
Динамическое программирование:
Введём массив dp[i][j], где:
i — текущая позиция в числе (1≤i≤N)
j=0: предыдущая цифра была нулём.
j=1: предыдущая цифра была отличной от нуля.
Само значение в dp[i][j] будет хранить количество правильных чисел длины i,
заканчивающихся на цифру, соответствующую состоянию j.
Базовый случай для первой цифры: dp[1][0] = 0, так как 0 не может быть на месте первой
цифры, а dp[1][0] = K – 1
Переход между состояниями:
- dp[i][0] = dp[i-1][1]
- dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * (K - 1)
Итоговый результат: сумма dp[N][0] + dp[N][1]
26

27.

Задача 18. Одинаковые суммы
План решения
Динамическое программирование:
Введём массив dp[i][j], где:
i — текущая позиция в числе (1≤i≤N)
j=0: предыдущая цифра была нулём.
j=1: предыдущая цифра была отличной от нуля.
Само значение в dp[i][j] будет хранить количество правильных чисел длины i,
заканчивающихся на цифру, соответствующую состоянию j.
Базовый случай для первой цифры: dp[1][0] = 0, так как 0 не может быть на месте первой
цифры, а dp[1][0] = K – 1
Переход между состояниями:
- dp[i][0] = dp[i-1][1]
- dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * (K - 1)
Итоговый результат: сумма dp[N][0] + dp[N][1]
27

28.

Задача 19. Дебютный альбом
Поп-группа «Розовый слон» приступила к записи своего дебютного альбома. Правда, у группы пока
всего две песни: «Моя любовь» и «Я скучаю по тебе», но зато на каждую сделано огромное
количество ремиксов.
Продюсер группы сказал, что в альбом должно войти ровно n треков, каждый из которых — это
ремикс на одну из двух песен группы. Поразмыслив, музыканты решили, что диск будет интересно
слушать только в том случае, если на нём не более a треков подряд будут ремиксами на песню «Моя
любовь» и не более b треков подряд будут ремиксами на песню «Я скучаю по тебе». Иначе есть риск,
что даже самые преданные фанаты не дослушают альбом до конца.
Сколько существует различных вариантов записи альбома из n композиций, который будет интересно
слушать? Вариант записи — это последовательность чисел 1 и 2, где единицы обозначают ремиксы на
песню «Моя любовь», а двойки — ремиксы на песню «Я скучаю по тебе». Два варианта считаются
различными, если для некоторого i в одном варианте на i-м месте стоит единица, а в другом —
двойка.
28

29.

Задача 19. Дебютный альбом
План решения
Динамическое программирование:
Введём два массива dp[i][j], где:
i — количество последних подряд идущих единиц (меньше a)
j – количество последних подряд идущих двоек (меньше b)
Два массива нужно, так как нам нужно хранить предыдущую и текущую длину.
Само
значение
dp[i][j]
будет
обозначать
количество
допустимых
последовательностей, заканчивающихся на j единиц или k двоек.
Базовый случай для первой цифры:
dp[1][0] = 1, если последовательность начинается с единицы,
dp[0][1] = 1, если последовательность начинается с двойки
// todo solve
Итоговый результат: сумма всех значений dp по модулю
29

30.

Задача 21. Трипростые числа
Отдых на море — это замечательно! Но вот программисту Паше ужасно скучно лежать на
пляже в Турции. Настолько скучно, что Паша решил посчитать количество трехзначных
простых чисел. Он так увлекся этим занятием, что начал изучать 3-простые числа. Так
Паша называет числа, у которых любые 3 подряд идущие цифры образуют трехзначное
простое число. Паша уже начал работу над теорией божественного происхождения таких
чисел, когда какие-то хулиганы окатили Пашу холодной водой и стали кричать какие-то
загадочные слова вроде «Sunstroke!», «Sonnenstich!» и «Colpo di sole!»
Вам предстоит продолжить дело Паши и выяснить насколько часты (или редки) 3простые числа
Формат входных данных
Ввод содержит целое число n (3 ≤ n ≤ 10000).
Формат выходных данных
Выведите количество n-значных 3-простых чисел, вычисленное по модулю 109 + 9.
30

31.

Задача 21. Трипростые числа
1.
2.
3.
4.
5.
План решения
Генерация всех трехзначных простых чисел. Это можно сделать с помощью решета
Эратосфена или проверки делимости (можно положить в set для ускорения).
Введем массив dp[i][j], где i – текущая позиция в числе, j – последние две цифры
числа на предыдущей позиции, а само значение – количество допустимых чисел
длины i, заканчивающихся на j (используем словарь)
Базовый случай (трехзначные числа): dp[3][j] = 1, если цифры образуют простое
число, где j – последние две цифры этого числа (берем остаток от 100)
От 4 до N для каждого l:
1. dp[l] = {}
2. Для каждых последних двух цифр lt:
1. Перебираем цифру d от 0 до 9
1. Получаем новое число nn, добавляя цифру в конец (lt * 10 + d)
2. Если полученное число nn простое
1. Добавляем пару в dp[l] (или обновляем, если она уже там была
ранее)
Результат – сумма всех чисел длины N (значений карты dp[N])
31

32.

Б Л А Г О Д А РЮ
З А
В Н И М А Н И Е !
32