Шостий тур - 2012

скачати файл завдання (*.doc)

Розв’язки відправляти з 17.12 по 23.12.12 р.

Розв’язок задачі відправляти як вкладений текстовий файл з іменем завдання.

1. Гірлянда (20 балів)

Ім’я вхідного файлу: girlan.dat

Ім’я вихідного файлу: girlan.ans

Програма: girlan.*

Обмеження часу: 2с

Обмеження пам’яті: 64 мбайт

Новорічну ялинку прикрашено гірляндою нескінченної довжини, що складається з послідовно з'єднаних лампочок. Коли гірлянду вмикають, загоряється лише перша лампочка, рахуючи від вимикача. Далі гірлянда починає загорятися за таким правилом. Кожного разу кількість підключених лампочок до гірлянди подвоюється. В другій половині лапочки горять в інверсному порядку відносно першої половини. (якщо лампочка в першій половині горить, то в другій половині лампочка що їй відповідає горіти не буде і навпаки). Знайдіть чи буде горіти в такій гірлянці N –на лампочка.

Формат вхідного файлу.

Єдиний рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 10^⁹) – номер лампочки.

Формат вихідного файлу

Єдиний рядок вихідного файлу має містити ціле число – 0 (якщо лампочка не горить) або 1 (якщо лампочка горить).

2. Мультигонія (100 балів)
Ім'я вхідного файлу: mulgon.dat
Ім'я вихідного файлу: mulgon.ans

Програма: mulgon.*

Обмеження часу: 2 с

Обмеження пам’яті: 64 мегабайта.

Володар Мультигонії Трігон ХVІ схиблений на реформах. Щоб увійти в літописи, він вирішив провести територіальну реформу в своїй країні. Країна Мультигонія має форму простого многокутника, тобто її границя не має самоперетинань і самоторкань. У Мультигонії велику роль відіграють внутрішні діагоналі - відрізки, що з'єднують вершини державного кордону і повністю проходять по території країни, не торкаючись кордону. При цьому форма Мультигонії така, що ніякі дві внутрішні діагоналі не лежать на одній прямій. Замість традиційного поділу держави на адміністративні округи король Трігон ХVІ вирішив розділити свою країну на адміністративні трикутники внутрішніми діагоналями. Для скорочення керуючого апарату король повелів підготувати такий план поділу країни, в якому кількість адміністративних трикутників буде мінімальним. Потрібно написати програму, що виконує поділ Мультигонії внутрішніми діагоналями на мінімально можливе число адміністративних трикутників.

Формат вхідних даних.

У першому рядку вхідного файлу записано число N (3<=N<=20) У наступних N рядках знаходяться по 2 цілих числа, по абсолютній величині не перевищують 10000– координати вершин в порядку обходу багатокутника проти годинникової стрілки. Гарантується, що ніякі три послідовні вершини багатокутника не лежать на одній прямій, і він не має самоперетинів і самоторкань. Також гарантується, що ніякі дві діагоналі, що містяться всередині багатокутника, не лежать на одній прямій.

Формат вихідних даних.

У перший рядок вихідного файлу виведіть найменшу кількість адміністративних трикутників, на яку можна розбити Мультигонію. У другому рядку виведіть кількість різних внутрішніх діагоналей K, за допомогою яких можна здійснити дане розбиття. У кожну з наступних K рядків виведіть 4 цілих числа - координати початку і кінця відповідної діагоналі розбиття, яка повністю лежить всередині многокутника і не проходить по його кордоні. Якщо шуканих розбиттів декілька, виведіть будь-яке з них.

Приклади: