В магазине есть $N$ кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество…
- 1
Считаем все длины сторон коробок и сортируем их по возрастанию.$$a_1 \leq a_2 \leq \dots \leq a_N$$
- 2
Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.$$a_i-a_{last}\geq 3$$
Ещё 2 қадам — толық шешімде
202ФИПИ 584C6A№ 26Күрделі В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую…
- 1
Считаем, что коробки вложены от меньшей к большей. Для соседних выбранных коробок должно выполняться условие разности сторон не менее 10.$$a_{i+1} - a_i \geq 10$$
- 2
Отсортируем все длины сторон по возрастанию.
Ещё 3 қадам — толық шешімде
Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известны срок его…
- 1
Для решения необходимо получить пары сроков хранения из прилагаемого входного файла и объединить все $2N$ значений в один список с указанием продукта и типа срока.
- 2
Значения следует обрабатывать по возрастанию. Если первым ещё не обработанным значением является срок хранения продукта, его место определяется слева; если это срок годности после вскрытия, его место определяется справа.
Ещё 2 қадам — толық шешімде
Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его…
- 1
Для каждого продукта создаём две записи: срок хранения с момента изготовления и срок годности после вскрытия. Каждой записи сопоставляем номер продукта и тип срока.
- 2
Сортируем все записи по возрастанию значения срока. Так как все исходные числа различны, порядок обработки однозначен.
Ещё 3 қадам — толық шешімде
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были…
- 1
Сгруппируем занятые места по номерам рядов и для каждого ряда определим максимальный номер занятого места.
- 2
В ряду с максимальным занятым номером $q$ подходящая пара может начинаться только после этого места. Поэтому проверяем места $q+1$ и $q+2$: если они существуют, то пара $q+1$, $q+2$ свободна, а перед ними нет занятых мест.
Ещё 2 қадам — толық шешімде
206ФИПИ 70B483№ 26Күрделі На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не…
- 1
Для максимального количества контейнеров выгодно выбирать самые лёгкие контейнеры: замена любого выбранного контейнера на более лёгкий не увеличивает суммарную массу.
- 2
Отсортируем массив масс по возрастанию.$$m_1 \leq m_2 \leq \dots \leq m_N$$
Ещё 2 қадам — толық шешімде
Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Сформируйте рейтинговый…
- 1
Для каждого студента подсчитываем количество оценок, равных 2, и сумму төрт оценок.$$twos_i = \#\{j \mid grade_{ij}=2\},\quad sum_i=\sum_{j=1}^{4}grade_{ij}$$
- 2
Студенты с нулевым количеством двоек сдали сессию. Их сортируем по убыванию суммы оценок, что эквивалентно сортировке по убыванию среднего балла, а при равенстве — по возрастанию ID.
Ещё 3 қадам — толық шешімде
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим…
- 1
Сгруппируем занятые места по нөмірлерге рядов и отсортируем нөмір мест внутри каждого ряда.$$r \to [m_1, m_2, \ldots, m_k]$$
- 2
Два соседних свободных места, ограниченные занятыми местами слева и справа, находятся между двумя занятыми местами, номера которых отличаются на 3.$$m_{i+1}-m_i=3 \Rightarrow (m_i+1,\ m_i+2)$$
Ещё 2 қадам — толық шешімде
В магазине для упаковки подарков есть $N$ кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите…
- 1
Сортируем длины сторон коробок по возрастанию. В цепочке коробки идут в порядке возрастания, а разность между соседними сторонами должна быть не меньше 9.$$a_{i_{k+1}} \geq a_{i_k}+9$$
- 2
Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.$$dp_i = 1 + dp_j,\quad j=\min\{k>i\mid a_k\geq a_i+9\}$$
Ещё 2 қадам — толық шешімде
Сервер выполняет запросы на передачу данных. Сведения о каждом запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале, а сам запрос помещается в…
- 1
Создаём таблицу или словарь, где каждому идентификатору клиента соответствует суммарный объём переданных им данных.$$T_C = \sum S_i$$
- 2
Из полученных сумм выбираем значения не менее 150 000 Кбайт и находим сумму двух наименьших таких значений.
Ещё 2 қадам — толық шешімде
Входной файл содержит информацию о заявках граждан, обращающихся в многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом в…
- 1
Считаем все заявки из файла и сортируем их по времени начала приёма.
- 2
Для каждого окна храним момент, с которого оно свободно. Изначально все окна свободны с начала суток.
Ещё 3 қадам — толық шешімде
212ФИПИ 97FA8B№ 26Күрделі Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим…
- 1
Два соседних свободных места, ограниченных занятыми местами слева и справа, имеют вид $x+1$ и $x+2$, если заняты места $x$ и $x+3$.$$x \text{ занят},\quad x+3 \text{ занят}$$
- 2
В ряду 40 заняты места 3 и 6, поэтому подходящая пара начинается с места 4.
Ещё 2 қадам — толық шешімде
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на такое место в ряду, чтобы перед ним как можно больше идущих подряд кресел с таким же номером…
- 1
Сформировать сведения о занятых местах для каждого ряда.
- 2
В каждом ряду просмотреть места по возрастанию номера. Для свободного места считать количество идущих подряд свободных мест непосредственно перед ним.
Ещё 2 қадам — толық шешімде
Сервер выполняет запросы на передачу данных. Сведения о каждом выполненном запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале работы, а сам запрос…
- 1
Для каждого клиента накапливаем суммарный объём переданных данных в словаре.
- 2
Последовательно обрабатываем запросы. Если текущий объём данных в разделе плюс объём очередного запроса превышает вместимость $K$, создаётся резервная копия текущего объёма. Время такой копии соответствует времени текущего запроса, из-за…$$V + S > K$$
Ещё 3 қадам — толық шешімде
Входной файл содержит заявки пассажиров, желающих сдать багаж в камеру хранения. В каждой заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж размещается в…
- 1
Создаём массив времени доступности ячеек, изначально равный нулю.
- 2
Для каждой заявки последовательно просматриваем ячейки от первой к последней и выбираем первую ячейку, для которой время доступности меньше времени сдачи багажа.
Ещё 2 қадам — толық шешімде
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были…
- 1
Считайте из файла количество занятых мест и занесите пары «ряд — место» в структуру данных, позволяющую быстро проверять занятость кресла.
- 2
Для каждого ряда и каждого начала пары $j$ от 1 до $K-1$ проверьте, свободны ли места $j$ и $j+1$ в текущем ряду.
Ещё 2 қадам — толық шешімде
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала…
- 1
Представим каждую заявку как интервал [начало, конец]. Условие совместимости двух последовательных мероприятий: начало следующего должно быть не меньше окончания предыдущего.$$s_{next} \ge e_{last}$$
- 2
Отсортируем все заявки по времени окончания. Жадно выбираем очередную заявку, если её время начала не меньше времени окончания последней выбранной заявки.
Ещё 2 қадам — толық шешімде
218ФИПИ B1F57A№ 26Күрделі В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую…
- 1
Считаем размеры коробок из файла и сортируем их по возрастанию. Одинаковые размеры сохраняем, поскольку коробки являются отдельными предметами.$$a_1 \leq a_2 \leq \dots \leq a_N$$
- 2
Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.$$a_j - a_i \geq 11$$
Ещё 3 қадам — толық шешімде
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж одного…
- 1
Считать количество ячеек K и количество заявок N. Для каждой ячейки сохранить время, с которого она свободна; изначально все ячейки свободны.
- 2
Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.$$free_i \le t$$
Ещё 2 қадам — толық шешімде
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала…
- 1
Представим каждую заявку как интервал [начало, окончание]. Мероприятия совместимы, если начало следующего не меньше окончания предыдущего.
- 2
Для максимизации количества мероприятий применяем жадный алгоритм: сортируем интервалы по времени окончания и выбираем очередной интервал, если он начинается не раньше окончания последнего выбранного.$$start_i \ge end_{last}$$
Ещё 2 қадам — толық шешімде