Условие:
У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет размер 1×1× LiLi. Петя знает, что он может построить из кирпичиков прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй — второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.
Формат ввода
В первой строке входных данных задаются числа N и K (1 <= N <= 5000, 1 <= K <= 100). Следующие N строк содержат описание Петиных кирпичиков: сначала длина LiLi, затем номер цвета CiCi (1 <= LiLi <= 100, 1 <= CiCi <= K). Известно, что у Пети не более 50 кирпичиков каждого цвета.
Формат вывода
Выведите в первой строке YES, если Петя сможет построить из своих кирпичиков две прямоугольные стены высоты K, j-й слой кирпичиков в каждой из которых будет j-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.
Реши эту задачу на языке python
Решение:
Для решения задачи, нам нужно проверить, можем ли мы построить две стены высотой K, используя кирпичики разных цветов. Каждая стена должна иметь K слоев, и каждый слой должен быть окрашен в определенный цвет.
Шаги решения:
1. Считывание входных данных: Мы получаем количество кирпичиков N и количество цветов K, а затем для каждого кирпичика его длину и цвет.
2. Группировка кирпичиков по цветам: Создадим список, который будет содержать длины кирпичиков для каждого цвета.
3. Проверка возможности построения стен: Для каждого цвета проверим, достаточно ли у нас кирпичиков, чтобы построить два слоя (по одному для каждой стены). Если для любого цвета у нас недостаточно кирпичиков, мы сразу можем вывести NO.
4. Сборка стен: Если мы можем построить две стены, мы также должны собрать индексы кирпичиков, которые мы будем использовать для первой стены.
5. Вывод результата: Если стены можно построить, выводим YES и индексы кирпичиков для первой стены. В противном случае выводим NO.
Теперь давайте напишем код на Python, который реализует этот алгоритм.
- Мы создаем словарь , который хранит кирпичики по цветам. - Затем мы проверяем, достаточно ли кирпичиков для каждого цвета, чтобы построить две стены. - Если все условия выполнены, мы собираем индексы кирпичиков для первой стены и выводим результат. Этот код решает задачу в соответствии с заданными условиями.