Задача №1872. Восстановление триангуляции
Триангуляцией правильного многоугольника называется разбиение его на треугольники, вершины которых совпадают с вершинами многоугольника. Легко понять, что для правильного \(N\)-угольника такое разбиение задается \(N - 3\) попарно не пересекающимися диагоналями, которые в нём проведены. Пронумеруем все вершины этого многоугольника числами от \(1\) до \(N\) в порядке обхода по часовой стрелке. Тогда каждая диагональ, в свою очередь, будет задаваться двумя числами — номерами вершин, которые она соединяет.
Пай-девочка Аня нарисовала карандашом на листе бумаги правильный \(N\)-угольник и триангулировала его. На другом листе она выписала все диагонали, которые составили эту триангуляцию, а потом пошла на кухню пить чай. Затем в комнату пришёл хулиган Андрей и решил сделать пакость. Он разорвал лист, на котором был нарисован многоугольник, и стёр с другого листа из записи каждой диагонали максимальный из двух номеров вершин.
Когда Аня увидела, что натворил Андрей, она очень расстроилась. Помогите ей восстановить исходную триангуляцию!
Входной файл состоит из нескольких наборов входных данных. Каждый такой набор состоит из двух строк. В первой строке содержится единственное число \(N\) \((N \ge 4)\) — количество вершин правильного многоугольника, который Аня триангулировала. Во второй строке содержатся \(N - 3\) числа, оставшиеся на втором листе. Гарантируется, что все входные данные корректны. Входной файл будет заканчиваться строкой, содержащей 0.
Общее количество чисел во всех наборах не превышает \(100\, 000\).
Для каждого набора входных данных выведите диагонали, составляющие анину триангуляцию. Каждая диагональ должна выводиться на отдельной строке, причём первым должен выводится наименьший из номеров вершин, составляющих эту диагональ. Диагонали должны быть выведены в лексикографическом порядке. Если таких триангуляций несколько, выведите любую из них. Следуйте формату примера максимально точно.
4 1 5 1 3 0
Case #1: 1 3 Case #2: 1 3 3 5