G. Две стены Ограничение времени: 1 секунда Ограничение памяти: 64 Мб Ввод: стандартный ввод или input.txt Вывод: стандартный вывод или output.txt У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет

8 октября 2025
Программирование

Условие:

G. Две стены

Ограничение времени: 1 секунда

Ограничение памяти: 64 Мб

Ввод: стандартный ввод или input.txt

Вывод: стандартный вывод или output.txt

У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов,
i-й кирпичик имеет размер 1 × 1 × Li. Петя знает, что он может построить из кирпичиков
прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков
в стене будет первого цвета, второй — второго и т. д. Теперь Петя хочет узнать, может ли он
из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите
ему выяснить это.

Формат ввода

В первой строке входных данных задаются числа N и K (1 ≤ N ≤ 5000, 1 ≤ K ≤ 100).

Следующие N строк содержат описание Петиных кирпичиков: сначала длина Li, затем номер цвета
Ci (1 ≤ Li ≤ 100, 1 ≤ Ci ≤ K). Известно, что у Пети не более 50 кирпичиков
каждого цвета.

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

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

Пример

Ввод
3 1
1 1
2 1
3 1

Вывод
YES
1

Решение:

Для решения задачи, давайте разберем шаги, которые нам нужно выполнить: 1. Понимание задачи: Нам нужно построить две стены высотой K, где каждый слой стены будет окрашен в определенный цвет. Каждый кирпичик имеет длину и цвет. Мы должны проверить, можем ли мы построить две такие стены, используя имеющиеся кирпичики. 2. Сбор данных: Мы будем хранить информацию о кирпичиках в виде массива, где для каждого цвета мы будем хранить длины кирпичиков. 3. Проверка условий: Для каждого цвета мы должны убедиться, что у нас достаточно кирпичиков, чтобы построить два слоя (по одному для каждой стены). Е...

- Мы считываем входные данные и разбиваем их на количество кирпичиков и цветов. - Создаем массив, где каждый элемент соответствует цвету и хранит длины и индексы кирпичиков. - Проверяем, достаточно ли у нас кирпичиков для каждого цвета, чтобы построить две стены. - Если все условия выполнены, выводим YES и индексы кирпичиков для первой стены. В противном случае выводим NO. Теперь, если вы запустите этот код с приведенным примером, он должен вернуть правильный ответ.