Страница: 1 Отображать по:
#545
Две стены
  
Источники: [ Командные олимпиады, ВКОШП, 2001, Задача A ]
Задано описание кирпичей, которое состоит из цвета, а также длины кирпича. Из кирпичей построена прямоугольная стена, причем каждый ряд имеет свой цвет. Требуется разделить кирпичи на 2 группы, чтобы из каждой группы можно было построить прямоугольную стену, содержащую ряды тех же цветов, что и исходная.

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

Входные данные

В первой строке входных данных задаются числа \(N\) и \(K\) (1 <= \(N\) <= 5000, 1 <= \(K\) <= 100). Следующие \(N\) строк содержат описание Петиных кирпичиков: сначала длина Li, затем номер цвета \(C_i\) (1 <= \(L_i\) <= 100, 1 <= \(C_i\) <= \(K\)). Известно, что у Пети не более 50 кирпичиков каждого цвета.

Выходные данные

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

Примеры
Входные данные
3 1
1 1
2 1
3 1
Выходные данные
YES
1
Входные данные
4 2
1 1
1 2
2 1
2 2
Выходные данные
YES
1 2
Входные данные
2 2
1 1
1 2
Выходные данные
NO
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест