1. Покриття iнтервалами, 8 балів
Відрізок числової прямої [a₀; b₀] належить об'єднанню скінченної кількості інтервалів [a₁;b₁], [a₂;b₂], …, [a_n;b_n].

Завдання
Створіть програму cover.*, яка з даної множини інтервалів вибере найменшу кількість інтервалів, об'єднання яких містить даний відрізок [a₀; b₀].

Вхідні дані
Файл cover.dat містить у вказаному порядку натуральні числа a₀, b₀, a₁, b₁, …, a_n, b_n, які не перевищують 65432, причому n < 10001.

Вихідні дані
Файл cover.res має містити лише послідовність натуральних чисел
a_j(1), b_j(1), a_j(2), b_j(2), …, a_j(k), b_j(k), для якої:

• будь-яка точка відрізка [a₀;b₀] належить щонайменше одному з інтервалів
  [a_j(1); b_j(1)], [a_j(2); b_j(2)], …, [a_j(k), b_j(k)];

• нерівності a_j(l) < a_j(l + 1) < b_j(l) справджуються при всіх l = 1, 2, …, (k – 1);

• a_j (1) < a₀ < b_j (1) i a_j (k) < b₀ < b_j(k).

Вхідні дані ґарантують існування і єдиність розв'язку.

Приклад

2. Трикутники, 18 балів

Завдання
Створіть програму triangle.*, яка з'ясує, чи можна з даних 4 трикутників утворити трикутник «склеюванням» вздовж сторони.

Вхідні дані
Кожний рядок файлу triangle.dat містить чотири трійки натуральних чисел, які є сторонами даних трикутників і менші за 321.

Вихідні дані
Відповідний рядок файлу triangle.res має містити:

• або сторони новоутвореного трикутника у порядку неспадання (якщо такий трикутник існує, то він єдиний);

• або запис «No solution», якщо такий трикутник не існує.

Приклад

3. Многоґранник-2, 28 балів
Всі ґрані многоґранника — правильні многокутники. Кількості ґраней і ребер не перевищують відповідно 20 і 36. Всі ґрані многоґранника занумеровано послідовними натуральними числами, починаючи з 1. Ребра також занумеровано послідовними натуральними числами, починаючи з 1. При цьому менший номер суміжної ґрані не спадає, а для сталого меншого номера суміжної ґрані більший номер зростає. Для правильного 4-ґранника перелік у такому порядку пар суміжних ґраней має вигляд (1;2), (1;3), (1;4), (2;3), (2;4), (3;4).

Завдання
Створіть програму polyedr.* знаходження розгорток многоґранника.

Вхідні дані
j-ий рядок файла polyedr.dat містить повний перелік номерів ґраней, що мають з j-ою ґранню спільне ребро.

Вихідні дані
Файл polyedr.res має містити дані про різні розгортки многоґранника, в якому всі ґрані одного кольору — по одному рядку на кожну розгортку. Кожний такий рядок даних має містити у порядку зростання номери нерозрізаних ребер для відповідної розгортки. Файл має містити перші 15 таких наборів даних, які відповідають різним розгорткам многоґранника. Перші набори в розумінні такої послідовності перебору розгорток у процесі «доклеювання» ґраней:

• перше не розрізане ребро обмежує ґрань 1 і має найменший номер з тих, які ще не розглянуто як перше ребро;

• кожне наступне не розрізане ребро вибирається з найменшим номером серед тих, які:

  • ще не розглянуто як «продовження» для вже вибраних попередніх ребер;

  • неможливо було вибрати на попередніх кроках склеювання розгортки без порушення її зв'язності.

Якщо кількість одноколірних розгорток менша за 15, то файл polyedr.res містить дані про всі такі розгортки. На кожне число файлу відвести по 3 позиції, останню обов'язково заповнити. Для кожного рядка всі числа записувати в порядку зростання, що не завжди відповідає описаному порядку вибору склеєних ребер.

Файл polyedr.out має містити лише кількість всіх симетрій многоґранника, яка не перевищує 120.

Приклад

4. Ханойськi башти, 10 балів
Диски з вирізаною серединою (форма бублика) перекладають таким чином:

• одночасно переноситься лише один диск, поки решта дисків нанизані на 3 стержні;
• на кожному стержні диски розташовано у порядку зростання радіусів основ зверху донизу;
• спочатку всі диски настромлені на стержень 3;
• всі диски треба настромити стержень 1.

Завдання
Створіть програму tower.* для визначення найменшої кількості переміщень дисків і розташування дисків після певної кількості переміщень, здійснених за оптимальним щодо кількості переміщень планом.

Вхідні дані
Файл tower.dat містить у вказаному порядку кількості дисків n і переміщень k, де n < 60, k < 10¹⁸.

Вихідні дані
Єдиний рядок файлу tower.res має містити у вказаному порядку, починаючи з першої позиції:

• шукану найменшу кількість переміщень n дисків від початкового моменту до кінцевого;

• у порядку зростання номери дисків, які розташовані відповідно на стержнях 1, 2, 3 після k переміщень, здійснених за оптимальним щодо кількості переміщень планом.

Диски занумеровано натуральними числами в межах від 1 до n включно у порядку зростання радіусів основ. Вмісти дисків розділено символом «*». Між числами, між числом і роздільником «*» лише 1 пропуск.

Приклади

5. Вписане коло, 9 балів

Завдання
Створити програму circle.*, яка для натурального радіуса вписаного кола знайде натуральні сторони трикутника.

Вхідні дані
Файл circle.dat містить лише одне натуральне число — радіус вписаного кола, який не перевищує 180.

Вихідні дані
Файл circle.res містить натуральні довжини сторін трикутника: у порядку незростання довжин по одному варіанту в одному рядку. Варіанти впорядкувати таким чином: найбільша сторона не зростає, а для сталої найбільшої сторони середня сторона спадає.

Приклад

6. Многоґранник-3, 35 балів
Всі ґрані многоґранника — правильні многокутники. Кількості ґраней і ребер не перевищують відповідно 20 і 36. Всі ґрані многоґранника занумеровано послідовними натуральними числами, починаючи з 1. Ребра також занумеровано послідовними натуральними числами, починаючи з 1. При цьому менший номер суміжної ґрані не спадає, а для сталого меншого номера суміжної ґрані більший номер зростає. Для правильного 4-ґранника перелік у такому порядку пар суміжних ґраней має вигляд (1;2), (1;3), (1;4), (2;3), (2;4), (3;4).

Завдання
Створити програму polyedr.*, яка зобразить розгортки многоґранника на екрані монітора.

Вхідні дані
j-ий рядок файлу polyedr.dat містить повний перелік номерів ґраней, що мають з j-ою ґранню спільне ребро.

Файл polyedr.res містить дані про розгортки многоґранника — по одному рядку на кожну розгортку, в якому перераховано номери нерозрізаних ребер для відповідної розгортки.

Кожний рядок файлу polyedr.ver взаємно однозначно відповідає вершині многоґранника й містить номери всіх ґраней, що сходяться до цієї вершини (містять цю спільну вершину).

Вихідні дані
Зображення розгортки многоґранника для кожного рядка вхідного файлу polyedr.res має бути таким: чорному тлі білі лінії-ребра, з точністю до 5% на весь екран монітора, з точністю до 5% єдиним масштабом по вертикалі й горизонталі, у центрі зображення кожної ґрані — її номер, у лівому верхньому куті екрану — номер зображення, який знаходиться поза зображенням розгортки. При натисканні клавіші Enter здійснюється перехід до наступної розгортки, а після останньої розгортки програма припинить роботу. Ґрань 1 зображено так:

• зображення ґрані 1 має горизонтальну сторону l таку, що зображення ґрані 1 розташоване не нижче цієї сторони;

• наступною за l стороною зображення ґрані 1 при обході периметра проти руху годинникової стрілки є зображення ребра, спільного для ґрані 1 і ґрані з найменшим можливим номером. Навіть якщо зображення цієї ґрані на розгортці не має спільної сторони з ґранню 1.

Приклад

polyedr.dat	polyedr.ver	polyedr.res	зображення («неґативи»)
2 3 4 1 3 4 1 2 4 1 2 3	1 2 3 1 2 4 1 3 4 2 3 4	1 2 3 1 2 5