Задача Триангуляція (TRIANG)

Триангуляцією опуклого многокутника називається розбиття його на трикутники діагоналями, що попарно не перетинаються. Степінню вершини відносно заданої триангуляції будемо вважати кількість діагоналей, які виходять з цієї вершини.Дано правильний N-кутник. Перенумеруємо всі його вершини у порядку обходу проти годинникової стрілки натуральними числами від 1 до N. Нехай дано невід’ємні цілі числа d1, d, …, dN. Потрібно визначити, чи існує хоча б одна така триангуляція, що для усіх i від 1 до N вершина i має відносно неї степінь di, і якщо існує, вказати будь-яку з них.Технічні умови. Програма TRIANG у першому рядку читає з клавіатури ціле число N (3≤N≤200000), у другому – N цілих чисел d1, d, …, dN (0≤diN). Програма виводить на екран К – кількість діагоналей, які задають шукану тріангуляцію, а даліK рядків з діагоналями. Кожна діагональ задаєтся двома числами ­– номерами вершин, які нею з’єднуються. Кожна діагональ повинна виводитися у окремому рядку. Номери вершин розділяються одним пропуском. У випадку, якщо триангуляції із заданими степенями вершин не існує, виведіть одне число -1.Приклад
Уведення Виведення
61 0 2 1 0 2 31 33 64 6
52 0 2 0 2 -1
 

© LIKT 1998-2018