Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Задача о рюкзаке
---> 1 задач <---
Источники --> Командные олимпиады --> ВКОШП
    1999(7 задач)
    2000(8 задач)
    2001(8 задач)
    2002(9 задач)
    2003(9 задач)
    2004(10 задач)
    2005(10 задач)
    2006(10 задач)
    2007(11 задач)
    2008(10 задач)
    2009(11 задач)
    2010(11 задач)
    2011(11 задач)
    2012(11 задач)
    2013(11 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: 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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест