Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Разбиение на пары

(Время: 8 сек. Память: 256 Мб Сложность: 83%)

Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров,каждый параметр характеризуется целым числом. Артефакт i имеет параметры ai,1, ai,2, ... , ai,k. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено ai,1 ≠ aj,1, при этом другие параметры у артефактов могут совпадать.

Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число bt, что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие ai,t ⩽ bt ⩽ aj,t или условие ai,t ⩾ bt ⩾ aj,t.

Теперь ученые хотят выяснить, верно ли расшифрован текст. Для этого необходимо проверить, существует ли корректное разбиение артефактов на пары. Каждый артефакт должен войти ровно в одну пару в разбиении.

Требуется написать программу, которая по описанию параметров артефактов определяет, можно ли разбить их на пары таким образом, чтобы для каждого параметра существовало значение, лежащее между значениями этого параметра артефактов каждой пары, и в случае положительного ответа выводит такое разбиение.

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

В первой строке входного файла INPUT.TXT заданы целые числа n и k — количество артефактов и количество параметров (2 ⩽ n ⩽ 2×105, n чётно, 1 ⩽ k ⩽ 7).

В следующих n строках задано по k целых чисел ai,1, ai,2, ... , ai,k — параметры артефактов (-109 ⩽ ai,j ⩽ 109, все значения ai,1 различны).

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

В выходной файл OUTPUT.TXT выведите «NO», если требуемого разбиения на пары не существует.

В противном случае выведите «YES» в первой строке. Далее выведите n/2 строк, в каждой строке выведите по два числа — номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.

Если существует несколько корректных разбиений артефактов на пары, разрешается вывести любое из них

Примеры

INPUT.TXTOUTPUT.TXT
16 2
8 6
1 5
6 3
3 1
4 7
7 2
YES
1 4
2 6
3 5
24 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1
NO

Пояснения к примерам

В первом примере пары имеют следующие параметры (8,6) − (3,1), (1,5) − (7,2), (6,3) − (4,7). При указанном разбиении на пары подойдут, например, значения b1 = 4, b2 = 4.

Во втором примере требуемого разбиения на пары не существует.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Два измерения
 B. Полные квадраты
 C. Автоматизация склада
 D. Машинное обучение
 E. Неисправный марсоход
 F. Интервальные тренировки
 G. Экспедиция
 H. Разбиение на пары

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



Как сделать распашные ворота для гаража своими руками