🏅 Решаем 5 олимпиадных задач на Python

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

Задача 1: Газон

Перед коттеджем Ивана Ивановича есть газон – его можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы. Однажды владелец купил новую газонокосилку, и в качестве тест-драйва подстриг прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). При этом пучки травы, находящиеся на границе этого прямоугольника, также были подстрижены. После стрижки владелец установил на газоне поливальную установку. Она находится в точке с координатами (x3, y3) и имеет радиус действия r. Таким образом, установка начала поливать все пучки, расстояние, от которых до точки (x3, y3) не превышает r. Напишите программу, которая поможет Ивану Ивановичу определить, сколько пучков травы оказалось и подстрижено, и полито.

Пересечение – подстриженные и политые пучки травы

Формат входных данных

• В первой строке содержатся четыре целых числа x1, x2, y1, y2 (−100000 ≤ х1 < х2 ≤ 100000, −100000 ≤ y1 < y2 ≤ 100000).
• Вторая строка содержит три целых числа x3, y3, r (−100000 ≤ x3, y3 ≤ 100000, 1 ≤ r ≤ 100000.

Формат выходных данных

Целое число (количество подстриженных и политых пучков травы).

Пример ввода:

Вывод:

🐍 Библиотека питониста

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»

🐍🎓 Библиотека собеса по Python

Подтянуть свои знания по Python вы можете на нашем телеграм-канале «Библиотека собеса по Python»

🧩🐍 Библиотека задач по Python

Интересные задачи по Python для практики можно найти на нашем телеграм-канале «Библиотека задач по Python»

Решение

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

Время работы такого решения равно O(r), то есть оно пропорционально радиусу окружности (области полива) и не зависит от количества пучков травы или прямых.

Первый вариант решения – краткий:

Второй вариант – быстрый:

Задача 2: Оптимальная стратегия

Два пирата придумали новую игру: выложили на стол в ряд все пиастры, и договорились, что во время очередного хода игрок может взять 1 монету либо справа, либо слева. Игра заканчивается, когда все монеты разобраны.

Оба пирата стремятся выиграть, и поэтому они будут брать монеты в соответствии с оптимальной стратегией. Разница между жадным алгоритмом и оптимальной стратегией выглядит так:

Напишите программу для определения победителя и суммы его выигрыша при условии, что оба участника играют оптимально, а монеты имеют разное достоинство.

Примеры ввода и вывода:

Решение

Эту задачу можно решить двумя способами.

Способ 1 – рекурсия с мемоизацией

Во время хода у каждого игрока есть две опции:

1. Взять монету Ci слева – тогда оппонент выберет монету Ci+1 или Cj. При этом каждый игрок стремится сделать выбор, который оставить противника с минимальной прибылью, то есть игрок может забрать монету Ci + min(function(i+2, j), function(i+1, j-1) ) где [i+2,j] – диапазон монет, доступных игроку, если противник выберет монету Ci+1, a[i+1,j-1] – монеты, доступные игроку в том случае, если оппонент возьмет монету справа, Cj.

Выбор слева

Статья по теме

⬇️🐍⬆️ Мемоизация vs bottom-up: какой подход динамического программирования требует меньше умственных усилий?

2. Взять монету Cj справа – в этом случае противник выберет либо Ci слева, либо Cj-1 справа. Чтобы оставить противника с минимальной прибылью, игрок возьмет монету, соответствующую условию Cj + min(function(i+1, j-1), function(i, j-2) ), где [i,j-2] – монеты, доступные пользователю, если противник выберет монету справа, а [i+1,j-1] – монеты, доступные при выборе Ci.

Выбор справа

Таким образом, рекурсивный случай выглядит так:

Граничные случаи:

Код решения с рекурсией:

Способ 2 – динамическое программирование

Алгоритм решения:

Нужно создать матрицу размера n x n.

В цикле рассматриваются элементы i и j на всех возможных позициях. Элементы разделены определенным количеством других элементов – дистанцией. В зависимости от результатов сравнения присваиваем значения переменным x, y, z:

• если i+2 <=j, то x равно matrix[i+2][j], в противном случае x = 0;
• если i+1 <=j-1, то y = matrix[i+1][j-1] , в противном случае y = 0;
• если i <= j-2, то z = matrix[i][j-2] , в противном случае z = 0.

Присваиваем matrix[i][j] максимальное значение из двух выражений – coins[i] + min(x, y) и coins[j] + min(y, z). Ответ – в matrix[0][n – 1].

Код решения с динамическим программированием:

Статья по теме

🐍 5 задач для подготовки к собеседованию по Python

Задача 3. Эскалатор

Станция метрополитена оснащена эскалатором. Пусть N человек бегут вниз по эскалатору, причем i-й пробегает одну ступеньку за ti секунд. Техника безопасности на эскалаторе запрещает «обгоны», то есть если человек A в процессе бега догнал человека B, который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B. Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно.

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

Формат входных данных

В первой строке программа получает число N (1 ≤ N ≤ 105). В последующих строках перечислены пары чисел ti, wi(1 ≤ ti, wi ≤ 106) – время пробега одной ступени и количество ступеней до конца эскалатора для i-того человека.

Формат выходных данных

Время в секундах, через которое i-й человек сойдет с эскалатора.

Пример ввода:

Вывод:

Решение

• Создаем массив order из индексов [0..n-1] для хранения порядка отсортированных людей.
• Вызываем быструю сортировку qs, которая сортирует людей по скорости, записывая индексы отсортированных людей в массив order.
• После сортировки для каждого человека вычисляем максимум из его собственного времени выхода и времени выхода предыдущего человека (учитывая, что обгонять нельзя).

В итоге мы получаем время для каждого человека с учетом правил эскалатора:

Статья по теме

🐍💼 Подготовка к собеседованию по Python: решаем 5 интересных задач

Задача 4: Вырубка деревьев

Фермер решил вырубить некоторые деревья, растущие перед его домом. Деревья перед домом посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед домом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите фермеру выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев, и соседние деревья находились на равном расстоянии друг от друга. Так, например, выглядят варианты для m = 5 и n = 3:

Варианты вырубки для m = 5 и n = 3

Пример ввода:

Вывод:

Решение

Обозначим расстояние между деревьями после вырубки d. Тогда существует n – d х (m – 1) – m + 1 способов вырубить деревья. Чтобы найти все варианты, нужно просуммировать способы по всем d. Кроме того, нужно учесть 2 частных случая – когда количество оставшихся после вырубки деревьев равно 0 или 1.

Вариант решения 1:

Вариант решения 2:

Задача 5. Симпатичные узоры

Мастер-плиточник выкладывает на полу размером m x n узоры из черных и белых плиток размером 1 х 1 метр. Проблема в том, что каждый новый клиент хочет, чтобы узор был уникальным, и не повторял предыдущие заказы мастера. Кроме того, узор должен быть симпатичным. Узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета.Это пример симпатичных узоров:

Симпатичные узоры

А на этой картинке – образцы несимпатичных:

Несимпатичные узоры

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

Решение:

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

Основная идея:

Каждое подмножество кодируется битовой маской длины n бит. Если i-й бит установлен в 1, значит i-й элемент входит в это подмножество.

В adj_mask[prv][cur] хранится информация о том, совместимы ли подмножества prv и cur (то есть не пересекаются ли они). Это проверяется заранее для всех пар подмножеств.

Для каждого числа подмножеств k от 1 до m, мы заполняем массив dp[k][mask] – число способов разбиений на k подмножеств, где последнее подмножество имеет битовую маску mask.

Переход от k-1 подмножеств к k происходит с помощью adj_mask:

dp[k][cur] += dp[k-1][prv], если подмножества prv и cur совместимы.

В итоге ответом служит сумма по всем битовым маскам в dp[m-1][mask].

Таким образом, методом динамического программирования подсчитывается число разбиений заданного множества на m подмножеств.