eolymp
bolt
Try our new interface for solving problems
Məsələlər

Восьминiг

Восьминiг

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Нещодавно Петрик повернувся додому з вiдпочинку на морi. Петрик дуже любить тварин, а тому бiльш за все цей вiдпочинок запам’ятався йому саме їх великою кiлькiстю. Серед них була i його найулюбленiша — восьминiг.

Повернувшись додому, Петрик одразу ж захотів побудувати багато восьминогів. Для цього він вирішив використовувати свій конструктор. Конструктор являє собою набір гнучких паличок, якими можна з’єднувати диски. Кожен з n дисків має a[i] отворів, у які можна вставляти палички. Паличка не може з’єднувати диск з самим собою та будь-яку пару дисків може з’єднувати не більше однієї палички.

В уявленні Петрика, восьминіг виглядає наступним чином

• тіло восьминога складається с трьох або більше дисків, з’єднаних по колу паличками;

• щупальце восьминога складається з декількох дисків, з’єднаних між собою паличками; щупальце може розгалужуватись та не може зростатись;

• кожне щупальце приєднується до якогось диску у тілі восьминога однією паличкою;

Зверніть увагу, що у восьминога може бути декілька щупалець, а може і навпаки не бути жодного щупальця. Більш того, декілька щупалець можуть бути приєднані до одного диска у тілі. На малюнку показані деякі восьминоги.

####Завдання

prb3.jpg

Допоможіть Петрику скласти восьминогів, щоб виконувались наступні умови:

• для побудови були використані усі диски;

• кожен отвір кожного диску був заповнений паличкою;

• кількість побудваних восьминогів була б максимально можливою. Зверніть увагу, що цей пункт є обов'язковим тільки у деяких підзадачах.

Вхідні дані У першому рядку вхідного файла задано одне число n(1 ≤ n ≤ 10^5) - кількість дисків у конструкторі Петрика.

У другому рядку записано n цілих чисел a[i](1 ≤ a[i] < n) - кількість отворів у i-му диску.

Третій рядок містить одне ціле число maximize, яке дорівнює 0, якщо не треба максимізувати кількість восьминогів, і 1 в противному випадку.

Вихідні дані У перший рядок вихідного файлу виведіть «Yes», якщо можна побудувати восьминогів, i «No» в противному випадку. У випадку позитивної відповіді виведіть число c - кількість восьминогів. Далі виведіть n рядків. На i-му з них запишіть два цілих числа num[i](1 ≤ num[i] ≤ c), p[i] - номер восьминога, якому належить диск i, та номер сусіднього диску, який знаходиться ближче до тіла восьминога. Якщо диск i належить тілу, будемо вважати, що p[i] = -1.

Для кращого розуміння ознайомтесь з прикладами із умови.

####Оцінювання

Пiдзадача Бали Додатковi обмеження Максимiзацiя кiлькостi Необхідні підзадачівосьминогiв0 0 Тести з умови Потрібна -1 9 Для усiх i виконується ai Не потрібна -∈ {1, 3}2 13 Для усiх i виконується ai Потрібна 1∈ {1, 3}3 27 - Не потрібна 1

4 51 - Потрібна 0, 1, 2, 3

Nümunə

Giriş verilənləri #1
9
2 1 2 1 1 1 4 3 3
1
Çıxış verilənləri #1
Yes
1
1 -1
1 7
1 -1
1 7
1 8
1 9
1 -1
1 -1
1 -1
Giriş verilənləri #2
11
2 2 2 3 3 3 2 2 1 1 1
1
Çıxış verilənləri #2
Yes
2
2 -1
2 -1
2 -1
2 -1
2 -1
1 -1
1 -1
1 -1
2 4
2 5
1 6
Giriş verilənləri #3
4
2 3 2 3
1
Çıxış verilənləri #3
No
Mənbə Джерело XXXI Всеукраїнська олімпіада з інформатики, Миколаїв, 2-6 квітня 2018