Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта

Это задача с двойным запуском

...Начало 2000-х. Мобильная связь начинает появляться не только в крупных городах, но и вдоль отдельных трасс. Так как покрытие далеко не идеально, а технологии были на невысоком уровне, то при передаче информации могли случаться сбои.

При отправке SMS-сообщений у жителей посёлка N происходили следующие эффекты: время от времени произвольная буква в тексте сообщения могла замениться на следующую по циклу с сохранением капитализации (то есть буква или остаётся неизменной, или заменяется следующей по алфавиту; если буква в алфавите последняя, она заменяется первой).

Например, текст mts мог придти как mts, или как nts, или как mus, или как mtt, или даже как nut.

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

Передаваемое сообщение состоит из не более, чем 160 строчных латинских букв. Протокол сети поддерживает передачу строк, состоящих из не более, чем 160 строчных и заглавных латинских букв (то есть передаваемое в режиме передачи сообщение должно удовлетворять этим ограничениям).

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

Первая строка входных данных содержит одну строку — «send», если нужно передать сообщение, и «receive», если нужно принять сообщение.

В случае передачи сообщения вторая строка содержит одно слово, составленное из строчных латинских букв. Длина слова не менее 1 и не более 160.

В случае приёма сообщения вторая строка содержит одно слово, составленное из строчных или заглавных латинских букв. Длина сообщения не менее 1 и не более 160 символов. Сообщение отличается от отправленного в режиме «send» только возможными искажениями, описанными в условии задачи.

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

В режиме передачи выведите одну строку, состоящую из строчных и заглавных латинских букв и имеющую длину от 1 до 160.

В режиме приёма выведите одну строку — сообщение, которое вам надо было передать.

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

Примеры

В этой задаче программу запускают дважды.

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

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

Программе надо вывести строку, которую она получила во время в первого запуска. Я решала задачу так: если у буквы нечётный номер в алфавите, сделаем её заглавной, иначе оставим строчной. Тогда, если во второй запуск программы размер буквы не соответствует ее чётности, то мы знаем, что ее заменили и можем вернуть обратно.

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта

Это — интерактивная задача

Во время испытания одной из базовых станций сети 6G произошёл сбой — зона передачи внезапно из окружности радиуса 1 стала правильным n-угольником, вписанным в окружность радиуса 1 с центром в точке (0, 0) и одной из вершин в точке (0, 1).

Вы находитесь около базовой станции — в точке (0, 0). Ваша задача — определить минимально возможное значение n.

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

Ваша задача — определить минимально возможное значение n.

Протокол взаимодействия

Взаимодействие начинает ваша программа. Вы отправляете дрон в полёт. Для этого задаёте направление — целое число градусов u от 0 до 359 (например, 0 соответствует положительному направлению оси x, 90 — положительному направлению оси y) в формате ? u. В ответ программа жюри возвращает 0 или 1 — целую часть длины пути, который преодолел дрон в заданном направлении до момента исчезновения связи.

Если вы готовы вывести ответ, используйте команду ! n, где n > 3 — минимально возможное количество вершин многоугольника n.

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

Пример

Замечание

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

Целая часть пройденного расстояния равна 1, если дрон пролетает через вершину, и 0 во всех остальных случаях.

Так как вершины правильного n-угольника имеют полярный угол k · 360/n (0 ≤ k < n), то

наличие вершины при повороте на X градусов обозначает, что для какого-то k k · 360/n = x. Если X и k не взаимно просты, то, разделив X и k на их наибольший общий делитель, получаем, что существует меньшее целое x, для которого поворот на x градусов приводит к попаданию в вершину и при этом (k, x) = 1, то есть 360 делится на x.

Тогда и все направления с углами вида ax, где a — целое число, также содержат вершины. Поэтому достаточно проверить все углы, являющиеся делителями 360, чтобы получить информацию, эквивалентную всем 360 запросам.

Так как 360 = 2³ · 3²· 5, то можно сделать 6 запросов: проверка угла 180 (кратность n двум), проверка угла 90 (кратность n четырём), проверка угла 45 (кратность n восьми), проверка угла 120 (кратность n трём), проверка угла 40 (кратность n девяти), проверка угла 72 (кратность n пяти), после чего получить максимальный делитель 360, на который делится n. Можно сэкономить один запрос: проверяем угол 90, если в этом направлении ответ 1, проверяем 45, а если нет — проверяем 180. Так находим d = НОД (n, 360) за 5 запросов. Если d ≤ 2, то многоугольника с n вершинами не существует, соответственно, надо найти минимальное n, для которого (n, 360) = d, это 7 и 14 для d = 1 и d = 2 соответственно. Если d > 2, то минимальное n, удовлетворяющее условиям задачи, равно d.

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта

Это — задача с двойным запуском. Первый запуск является интерактивным

Вы решили принять участие в открытом чемпионате МТС по интеллектуальным играм. Сегодня ваша команда играет в две игры — крестики-нолики и пентамино.

Крестики-нолики проходят на доске 3×3 по классическим правилам. Вы играете одну или более партий против гроссмейстера. Вы всегда играете крестиками и ходите первым. Гроссмейстер играет оптимально (то есть при вашей оптимальной игре партия, как известно, закончится вничью, при вашей ошибке компьютер постарается выиграть), из различных оптимальных вариантов он может выбрать любой.

Финальные позиции всех сыгранных партий публикуются на сайте чемпионата.

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

Задачу с пентамино будут решать оставшиеся члены вашей команды.

Вы же, как капитан, получили входное задание — непустой набор попарно различных пентамино. Напоминаем, что пентамино — это фигура из пяти клеток на клетчатой бумаге, обладающая следующим свойством: между любыми двумя клетками пентамино можно пройти по клеткам пентамино, перемещаясь только в клетки, которые имеют общую сторону с текущей. В этой задаче два пентамино считаются равными, только если они совмещаются параллельным переносом. То есть если даже одно пентамино получено из другого поворотом или отражением, такие пентамино считаются разными. Однако за минуту до начала игры в крестики-нолики вы осознали, что забыли отправить задание сокомандникам.

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

При первом (интерактивном) запуске ваша программа получает на вход количество пентамино, а также сами фигуры, заданные в стандартном формате. После чего ваша программа выбирает количество партий (от 1 до 21), которые она должна сыграть. Далее запускаются партии в крестики-нолики. Если Ваша программа проиграет хотя бы раз или нарушит правила (например, сходит на занятую клетку) — вы получаете вердикт Wrong Answer.

Если все партии заканчиваются вничью, то финальные позиции всех сыгранных партий будут переданы вашей программе при её втором (неинтерактивном) запуске в том порядке, в котором партии были сыграны. Ваша программа должна вывести тот же набор пентамино, который был передан на вход программе при первом запуске. Порядок фигур в наборе значения не имеет. Если ваша программа выведет фигуру, которой не было в исходном наборе, или не выведет какую-то фигуру, которая была в исходном наборе, или выведет какую-то фигуру дважды, решение будет признано неверным.

Протокол взаимодействия

Взаимодействие при первом запуске начинает программа жюри.

В первой строке программа жюри выводит сообщение encode. Во второй — одно целое число K: количество пентамино в наборе. Гарантируется, что число является положительным и что каждое пентамино встретится в наборе не более одного раза (то есть что никакие два пентамино в наборе не переводятся друг в друга параллельным переносом).

Далее следуют K описаний пентамино.

Описание одного пентамино имеет следующий формат:

• Первая строка описания содержит два целых числа r и c (1 ≤ r, c ≤ 5) — количество строк и столбцов в минимальном прямоугольнике пентамино. Минимальный прямоугольник для некоторого пентамино определяется как прямоугольник, в каждой строке и в каждом столбце которого есть как минимум одна клетка, принадлежащая данному пентамино.

• Далее следуют r строк, каждая из которых содержит c символов. Символ равен ., если соответствующая клетка прямоугольника свободна, и *, если она занята элементом пентамино.

Гарантируется, что всего ровно 5 клеток содержат * и что фигура, образованная звёздочками, является связной в описанном в условии смысле.

После вывода описаний пентамино Ваша программа выводит одно целое число n (1 ≤ n ≤ 21) — количество партий в крестики-нолики. После чего играется n партий. Формат взаимодействия во время партии:

Поля имеют следующую нумерацию:
abc
3...3
2...2
1...1
abc

То есть левое нижнее поле имеет номер a1, правое нижнее — c1, поле в середине — b2 и так далее.

В каждой партии вы делаете первый ход.

Ход заключается в указании через пробел номера позиции, в которую ставится крестик, то есть, например «a 1». Если позиция уже занята или некорректна (на доске нет такого поля), Ваше решение получает сообщение об ошибке. В ответ компьютер выводит ход гроссмейстера в аналогичном формате. Если вы проигрываете, ваше решение получает сообщение об ошибке. В противном случае после вашего пятого хода доска оказывается полностью заполненной, фиксируется ничья, после чего начинается следующая партия (или взаимодействие успешно завершается, если уже сыграно n партий).

После вывода количества партий, а также после каждого хода не забывайте выводить символ перевода строки, а также сбрасывать буфер вывода с помощью вызова функции flush используемого языка программирования. В противном случае вы можете получить вердикт Wall Time Limit.

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

При втором (неинтерактивном) запуске первая строка содержит сообщение decode. Вторая строка содержит количество сыгранных партий n. Далее идут n блоков по 3 строки — финальные позиции партий в том порядке, в котором они были сыграны. Клетки, на которые делала ход ваша программа, обозначены символом x, клетки, на которые делал ход гроссмейстер, обозначены символом o. Гарантируется, что позиции соответствуют сыгранным партиям.

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

Выведите описание набора пентамино в том же формате, в котором пентамино были заданы во время первого запуска. Порядок следования пентамино в наборе может быть произвольным.

Помните, что повёрнутые или отражённые пентамино в этой задаче считаются различными.

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

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

Но я быстро пришёл к правильной гипотезе.

Для начала сгенерируем все варианты пентамино. Это можно сделать двумя способами:

1. Вспомнить все 12 свободных пентамино и затем применить к ним вращение и отражение и сохранить получившиеся объекты в set,

2. Генеририровать пентамино рекурсивно и сохраняя их в set (при этом сразу сгенерируются варианты со всеми поворотами).

В обоих случаях есть смысл вместе с фигурой хранить размеры минимального прямоугольника с осями, параллельными осям координат, в который эта фигура вписана, а координаты клеток перевычислять относительно этого прямоугольника (чтобы избежать случаев, когда две фигуры отличаются только положением внутри прямоугольника с координатами). Получаем 63 варианта.

Надо закодировать 2⁶³ различных наборов 21-й партией в крестики-нолики. То есть одна партия должна кодировать три бита информации (то есть число от 0 до 7). Генерируем все заполнения поля 3 × 3 крестиками и ноликами, при которых число крестиков на единицу больше числа ноликов и никакие три одинаковых символа не образуют выигрышную позицию. Таких заполнений 16. В 8 из них в центре стоит крестик, ещё в 8 — нолик.

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

Обозначим цифрами ходы крестиков, а буквами — ходы ноликов. При двух первых ходах крестиков 1 и 2 позиция автоматически приходит к следующей (с ходом ноликов):

B21
4AC
..3

В любом из двух вариантов окончания хотя бы одна из пары клеток, получающихся поворотом этой конструкции на 90 · n градусов из клеток b3, c3, будет занята ноликом. То есть по финальной позиции первые два хода определяются однозначно (единственная из этих пар, занятая двумя крестиками).

Так как всего существуют 4 поворота данной позиции, то всего мы можем так передать 4 варианта.

Пусть первый ход делается в центр. Ответ не в угловую клетку ведёт к проигрышу. Так что первый ход идёт в угловую клетку. После чего можно форсированно поставить ходы 2 и 3 (на них нолики вынуждены делать автоматические ответы), получив «уголок». Примеры ниже показывают, как получить любую из четырёх возможных его ориентаций. Понятно, что в случае ещё одной клетки, составляющей «уголок» с уже существующим, будет заполнена вертикаль или горизонталь, так что данный «уголок» однозначно идентифицируется.

.2A.
C13
.B.
.CA.
B12
.3.
B.A
31C
.42
.2A
31C
.B.

Так мы получили 4 варианта при первом ходе в угол (и занятом ноликами центре), и 4 варианта при первом ходе в центр, итого требуемые 8 вариантов. На уровне декодирования остаётся реализовать распознавание положения уголка или поворота пары клеток b2, b3, после чего принять 63 бита и сгенерировать набор уникальных пентамино одним из способов, указанных в начале.

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

Описание работы эмуляции – участникам не известно. Все числа приведены для примера. Основной параметр, определяющий нагрузку на приложение – количество входящих запросов. Количество входящих запросов изменяется в течение дня от 0 до нескольких тысяч по определенному закону.

На обработку каждого запроса требуются ресурсы приложения и ресурсы базы данных.

Время обработки запроса складывается из времени обработки в приложении и времени выполнения запроса в БД.

При выполнении запроса больше 400ms он считается неуспешным.

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

Ресурсы приложения

Выполнение каждого запроса требует 0.001 CPU и 5Mb памяти

Время выполнения запроса – 50ms

Накладные расходы приложения на каждой виртуальной машине – 0.05 CPU, 300Mb памяти

Если суммарное количество требуемых ресурсов CPU превышает 95% от выделенных, то приложение перестает отвечать и уходит в офлайн

Если суммарное количество требуемых ресурсов памяти превышает 95% от выделенной, то приложение перестает отвечать и уходит в офлайн

Ресурсы БД

Выполнение каждого запроса требует 0.001 CPU и 30Mb памяти

Время выполнения запроса – 50ms

Накладные расходы ядра БД на каждой машине с БД – 0.05 CPU, 512Mb памяти

Если суммарное количество требуемых ресурсов CPU превышает 95% от выделенных, то приложение перестает отвечать и уходит в офлайн

Если суммарное количество требуемых ресурсов памяти превышает 95% от выделенной, то приложение перестает отвечать и уходит в офлайн

Общие принципы работы с виртуальными машинами

При изменении количества ресурсов виртуальной машины — виртуальная машина перестает работать на 3 минуты. Тарификация машины продолжается

При заказе новой виртуальной машины — она становится доступной через 5 минут. Но тарификация начинается с момента создания машины

Время ответа приложения

Время ответа приложения зависит от нагрузки на CPU для виртуальных машин и базы данных. Виртуальные машины и базы данных вносят разные задержки в обработку запроса. Если время ответа на запрос превышает 400ms, то приложение уходит в офлайн.

API

Запрос ресурсов возвращается список из:

• тип ресурса - db/vm

• стоимость ресурса (cost)

• нагрузка на cpu

• нагрузка на память

• количество cpu

• количество памяти

• ID ресурса

• состояние неработоспособности ресурса (failed) после заказа или изменения

Запрос цен возвращается список ценовых позиций из:

• тип ресурса vm/db

• стоимость ресурса

• количество cpu

• количество ram

• ID позиции

Запрос текущей статистики возвращает текущую статистику по пользователю, запрос включает:

• "availability": доступность сервиса по шкале 0…1. 1 означает работу сервиса 100% времени без пропущенных запросов

• "cost_total": общие затраты накопительным итогом

• "db_cpu": всего ЦПУ для баз данных

• "db_cpu_load": текущая нагрузка на цпу базы данных

• "db_ram": всего памяти для базы данных

• "db_ram_load": текущая нагрузка на память базы данных

• "last1": затраты за последнюю минуту

• "last15": затраты за последние 15 минут

• "last5": затраты за последние 5 минут

• "lastDay": затраты за последний день

• "lastHour": затраты за последний час

• "lastWeek": затраты за последнюю неделю

• "offline_time": общее время оффлайна

• "online": признак работоспособности

• "online_time": общее время онлайна

• "requests": текущее количество запросов

• "requests_total": общее количество запросов, поступившее к приложению

• "response_time": время ответа приложения (должно быть меньше 400 для работоспособного приложения)

• "vm_cpu": всего ЦПУ для виртуальных машин

• "vm_cpu_load": нагрузка на ЦПУ для виртуальных машин

• "vm_ram": всего памяти для виртуальных машин

• "vm_ram_load": нагрузка на память для виртуальных машин

Все запросы к API (кроме получения списка цен) делаются с токеном пользователя.

Токен пользователя можно найти в правой части страницы, под доступами к gitlab.

Заказ/модификация ресурса возможны только в комбинациях CPU/RAM для которых есть соответствующая строка с ценами.

Ссылка на полную документацию API.

Оценка работы сервиса

Мы собираем 2 показателя, которые оценивают эффективность решения: количество затрачиваемых ресурсов и кол-во минут, которые «сервис» был офлайн.

Расчет со стороны API происходит каждую минуту: каждый «тик» времени сервис записывает в лидерборд кол-во потраченных за эту минуту «ресурсов» (число) и время, которое сервис был оффлайн (0 или 1). Лидерборд складывает эти данные и показывает итоговые числа по работе системы.

Для исключения разности результатов ввиду разного времени старта работы сервиса, итоговый лидерборд будет строиться отдельно. После завершения работы над решением (стоп-кодинг), мы отключим возможность обновлять алгоритмы, сбросим лидерборд и в течение 60 минут «засечем» работу всех решений с нуля. Таким образом, сформировав итоговый лидерборд по этапу, на основании которого и будут выявлены лидеры.

Для оптимизации затрат ресурсов и оптимизации времени работы сервиса был разработан следующий план:

1. Рассчитываем требуемые ресурсы CPU и RAM для обработки одного запроса и накладные ресурсы приложения на основе статистических данных.

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

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

Рассмотрим каждый пункт подробнее:

1. Расчет требуемых ресурсов CPU и RAM для обработки одного запроса

Для каждого ресурса (VM CPU, VM RAM, DB CPU, DB RAM) вычисляются накладные расходы при помощи линейной алгебры. Необходимо решить следующую систему уравнений:

cpuCount(t1)=cpuOverhead+requestsCount(t1)∗cpuRequest
cpuCount(t2)=cpuOverhead+requestsCount(t2)∗cpuRequest

В этих уравнениях:

• requestsCount(t1) и requestsCount(t2) обозначают количество запросов в моменты времени t1 и t2 соответственно.

• cpuOverhead представляет собой накладные расходы CPU виртуальной машины.

• cpuRequest представляет собой потребление CPU для одного запроса.

• cpuCount(t1) и cpuCount(t2) обозначают общее количество CPU в моменты времени t1 и t2 соответственно.

Аналогичные формулы и для вычисления RAM.

Фрагмент кода, выполняющий расчеты:

data = (
    (f_vm_cnt, s_vm_cnt, "vm_cpu", "vm_cpu_load",),
    (f_vm_cnt, s_vm_cnt, "vm_ram", "vm_ram_load",),
    (f_db_cnt, s_db_cnt, "db_cpu", "db_cpu_load",),
    (f_db_cnt, s_db_cnt, "db_ram", "db_ram_load",),
)
for f_cnt, s_cnt, res, load in data:
    m = np.array([[f_cnt, first_item.requests], [s_cnt, second_item.requests]])
    v = np.array(
        [
            _cal_percent(getattr(first_item, res), getattr(first_item, load)),
            _cal_percent(getattr(second_item, res), getattr(second_item, load)),
        ]
    )
    # https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html
    over, request = np.linalg.solve(m, v)
    result.append([over.item(), request.item()])

2. Прогнозирование количества запросов

Для прогнозирования используется модель ARIMA. Прогноз делается на 5 минут вперед, так как время создания одного ресурса занимает 5 минут, а изменение — 3 минуты.

Фрагмент кода:

dates = [
    item.timestamp
    for item in list(self._stats_service.memory.values())[
        -settings.train_size:
    ]
]
requests = [
    item.requests
    for item in list(self._stats_service.memory.values())[
        -settings.train_size:
    ]
]

df = pd.DataFrame(list(zip(dates, requests)), columns=["date", "requests"])
df.set_index("date", inplace=True)

train = df["requests"]

model = auto_arima(
    train, trace=False, error_action="ignore", suppress_warnings=True
)
model.fit(train)

# Прогноз делается на 5 минут вперед
result = model.predict(n_periods=5)

self.requests = [math.ceil(i) for i in list(result)]

3. Расчет необходимых ресурсов

Для оптимизации затрат на ресурсы требуется решить задачу линейного программирования. Сделать это можно с помощью библиотеки PuLP. Мы стремимся к минимизации общих издержек на ресурсы, при условии выполнения требований к количеству CPU и RAM.

Фрагмент кода:

def choose_optimal_resources(
    data: tp.List[models.Price],
    requests: int,
    request_cpu: float,
    request_ram: float,
    overhead_cpu: float,
    overhead_ram: float,
):
		# Создаем проблему линейного программирования
    model = LpProblem("Minimize_Cost", LpMinimize)
    
    # Создаем переменные для количества ВМ каждого типа
    resource_types_cnt = len(data)
    vm_vars = LpVariable.dicts(
        "VM", range(resource_types_cnt), lowBound=0, cat="Integer"
    )

		# Целевая функция: минимизировать общую стоимость
    model += lpSum(
        vm_vars[i] * (data[i].cost - settings.penalty)
        for i in range(resource_types_cnt)
    )
    
    # Условие 1: необходимое количество CPU
    model += (
        lpSum(
            vm_vars[i] * (settings.pod_load_max_percent * data[i].cpu - overhead_cpu)
            for i in range(resource_types_cnt)
        )
        >= requests * request_cpu
    )
    
    # Условие 2: необходимое количество RAM
    model += (
        lpSum(
            vm_vars[i] * (settings.pod_load_max_percent * data[i].ram - overhead_ram)
            for i in range(resource_types_cnt)
        )
        >= requests * request_ram
    )
		
		# Решаем проблему
    model.solve(PULP_CBC_CMD(msg=False))
    optimal = []

    for i in range(resource_types_cnt):
        num = int(value(vm_vars[i]))
        if num > 0:
            optimal.extend([data[i]] * num)
    return optimal

Полное решение можно найти здесь.