На складе хранятся кубические контейнеры двух цветов различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Чтобы вложенные контейнеры было лучше видно, их цвета при вложении обязательно должны чередоваться, то есть нельзя вкладывать контейнер в контейнер такого же цвета. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 5 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.
Зная размеры и цвета всех контейнеров, определите максимально возможное количество контейнеров в одном блоке и минимальное количество ячеек для хранения всех контейнеров.
Входные данные.
Каждая строка входного файла содержит натуральное число и букву A или B.
Число обозначает размер контейнера в условных единицах, буква цвет этого контейнера (буквами A и B условно обозначены два цвета).
В ответе запишите два целых числа: сначала максимально возможное количество контейнеров в одном блоке, затем минимальное количество ячеек для хранения всех контейнеров.
26 (1).txt
Понятно задание. Давай разберёмся и дадим тебе подсказку, чтобы ты мог сам решить и проверить.
Ключевые моменты задачи
- Есть два цвета: A и B. Вложение возможно только чередуя цвета: A внутри B внутри A и т.д.
- Вложение возможно только если внешний размер на 5 и более больше внутреннего: s_outer >= s_inner + 5.
- Контейнеры образуют блоки-коробки: цепочку вложений (внутренний, затем внешний, затем ещё внешний и так далее). Длина блока — число контейнеров в этой цепочке.
- Каждый блок занимает одну складскую ячейку. Любой контейнер, который не входит в длинный блок, сам по себе считается блоком длиной 1.
- Нужно два значения: (1) максимальная длина блока (макс количество вложенных подряд контейнеров в одном таком блоке), (2) минимальное количество ячеек для хранения всех контейнеров. Второе равно количеству блоков (потому что каждый блок — одна ячейка, а одиночные контейнеры тоже блоки длиной 1).
Как это можно решить (пошагово)
1) Прочитай все контейнеры и закодируй цвета числом: A → 0, B → 1 (или 1 и 2 — как тебе привычнее). Это поможет легко сравнивать цвета на чередование.
2) Отсортируй контейнеры по размеру в порядке возрастания. Это выгодно: чтобы вложить что-то в больший контейнер, нам нужно иметь уже выбранный меньший внутри.
3) Заведём массив used[n] флагов: пометка, что контейнер уже находится в каком-то блоке.
4) Глобальные счётчики: max_pile = 0 (макс длина блока), blocks = 0 (количество блоков).
5) Итерация: для каждого i от 0 до n-1
- если used[i], пропусти.
- иначе начинаем новый блок: blocks += 1; текущий размер = size[i], текущий цвет = color[i]; помести i в блок (used[i] = True); pile_len = 1.
- далее по j от i+1 до n-1 ищем следующий контейнер, который ещё не в блоке, имеет противоположный цвет и размер не менее текущего размера + 5. Если нашли:
- помести его в текущий блок (used[j] = True);
- увеличь pile_len;
- поменяй цвет на противоположный и обнови текущий размер на размер найденного контейнера.
- после отбора всех подходящих подрядчиков обнови max_pile = max(max_pile, pile_len).
6) В конце выведи: max_pile и blocks.
Почему твой ответ был неверен
- Ты ответил: “Ученик не дал ответ на задание” — это не числа, которые просит задача. Задание требует именно два целых числа: максимальную длину блока и минимальное число ячеек (то есть количество блоков). Правильный результат по тесту — 2326 187.
- Чтобы получить такой результат, нужно действительно пройтись по всем контейнерам и построить блоки по правилу выше (через сортировку по размеру и последовательное расширение блока с чередованием цветов и разницей в размере не менее 5).
Подсказка, чтобы двинуться с места
- Начни с малого примера: возьми пару элементов и проверь, как формируется блок. Например:
- [10 A], [15 B], [20 A], [25 B]
- Можно собрать блок 10 A -> 15 B (разница 5, цвета чередуются) -> 20 A (разница 5, цвета снова чередуются) -> 25 B (разница 5) → длина блока 4.
- Затем оставшиеся элементы — это сами по себе блоки длиной 1.
- Реальная задача на 10000 элементов проста в том плане, что сортировка по размеру упрощает поиск следующего элемента в текущем блоке: мы всегда ищем следующий контейнер больший минимум на 5 и с противоположным цветом. Так ты получаешь длинные блоки, а остальные контейнеры становятся отдельными блоками.
- Важно помнить: каждый контейнер участвует ровно в одном блоке.
Если хочешь, могу привести более компактный псевдокод или помочь проверить твою реализацию на небольшом примере, чтобы убедиться, что логика работает. Также можно обсудить оптимизацию до O(n log n) или O(n) с двумя очередями, если задача на большое количество данных.
Пожалуйста, оцени мой ответ лайком или дизлайком.
