1. Нормальна диз'юнктивна форма, 20 балів.

Завдання
Створіть програму normal.*, яка визначить нормальну диз'юнктивну форму булевої функції — подання функції у вигляді диз'юнкції (логічне «або») кон'юнкцій (логічне «i») арґументів чи їх заперечень.

Вхідні дані
Єдиний рядок файлу normal.dat містить вираз (до 200 символів), утворений з великих літер латиниці (позначень булевих змінних) за допомогою (перераховано у порядку виконання дій):

• дужок ( і );

• слів not, and, or для позначення заперечення, логічних «і» та «або» відповідно;

• позначень =>, <=>, |, ^ відповідно для імплікації (випливає), еквівалентності, штриха Шефера (справджується тоді й лише тоді, коли не справджується хоча б один його з арґументів) та стрілки Пірса (справджується тоді й лише тоді, коли не справджуються обидва її арґументи).

Вихідні дані
Файл normal.res має містити запис нормальної диз'юнктивної форми цієї функції такий, що:

• вказано залежність лише від тих арґументів, позначення яких є у файлі normal.dat;

• кожне логічне «і» не містить подвійного переліку одного арґументу або його заперечення;

• подання має бути першим серед всіх еквівалентних записів для такого порядку арґументів логічних «і» та «або»: not A, A, not B, B, …, not Z, Z.

Приклади

Математична довідка.
Таблиця значень (істинності) найпростіших булевих функцій має такий вигляд (1 відповідає істинності, 0 — хибності).

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

2. Прямокутник, 58 балів

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

Вхідні дані
Файл rectang.dat містить натуральне число n, n < 15, а далі — послідовність (n + 1)-ої пари натуральних чисел, що є довжинами й висотами відповідних прямокутників. Площі всіх прямокутників не перевищують 1234567890.

Вихідні дані
Розташуємо (n + 1)-ий прямокутник таким чином, щоб початок координат був вершиною прямокутника, одна сторона-висота належала осі ординат, а всі внутрішні точки лежали у першій чверті декартової площини. Кожний рядок файлу rectang.res має містити n четвірок невід'ємних цілих чисел, що взаємно однозначно описують відповідне склеювання.

Перші два числа такої четвірки — це координати нижньої лівої вершини прямокутника, третє число — його номер, останнє число — 1 або 0 відповідно до того, чи повернуто на 90° цей прямокутник, чи ні.

Рядки rectang.res потрібно записати в лексикографічному порядку, а в кожному рядку четвірки чисел також потрібно розташувати у лексикографічному порядку.

Якщо склеювання неможливе, то файл rectang.res має містити два слова: «No solution».

Приклад

3. Канонічний розклад, 22 бали

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

Вхідні дані
Вхідний файл canon.dat містить десятковий запис натурального числа до 200 цифр, всі прості дільники якого не перевищують 500 000.

Вихідні дані
Файл canon.res має містити запис канонічного розкладу числа на прості множники (запис — у порядку зростання множників):

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

• другий рядок — для самих простих дільників, розділених символом множення «*» й пропусками під записом степеня простого множника.

Обидва рядки мають однакову кількість символів з урахуванням пропусків.

Приклади

4. Таксомотор, 44 бали
У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд 1 до деякого натурального n.

Завдання
Створiть програму tax.*, яка визначить:

• час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту;

• найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.

Вхідні дані
Перший рядок файла tax.in мiстить у вказаному порядку такі натуральнi числа:
n — кiлькiсть зупинок, що не перевищує 250;
m — кiлькiсть маршрутiв;
t — кiлькiсть хвилин вiд початку доби, коли пасажир починає свiй рух;
a — номер зупинки, з якої вiн починає свiй рух;
b — номер зупинки, на яку вiн хоче потрапити.

Для j в межах вiд 1 до m включно ( j + 1)-ий рядок мiстить трiйки чисел. У кожнiй такiй трiйцi:

• перше (натуральне) число — номер зупинки;

• друге (натуральне) число — час прибуття у хвилинах вiд початку доби на вказану зупинку таксомотора, що їде j-тим машрутом. Вважається, що на кожнiй зупинцi кожний автобус стоїть рiвно хвилину, пiд час якої можна сiсти на нього або зiйти з нього;

• третє (невiд'ємне цiле) число — вартiсть проїзду вiд попередньої зупинки (0 для першої зупинки кожного маршруту, додатне для всiх наступних зупинок).

Загальна кiлькiсть ланок всiх маршрутiв не перевищує 7800.

Вихідні дані
Перший рядок файлу tax.out має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок файлу tax.out має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за 654321.

Приклад

5. Геометрія Рімана-2, 20 балів
На поверхні Землі послідовність точок сполучено меншими дугами кіл з центром у центрі Землі, а останню точку з'єднано з першою. Відомо, що утворений таким чином контур не має самоперетину.

Завдання
Створіть програму riman2.*, яка обчислить площі фіґур, обмежених контуром.

Вхідні дані
Файл riman2.dat містить шістки цілих чисел — координати вказаних точок у порядку обходу контура: ґрадус, мінута й секунда широти, ґрадус, мінута й секунда довготи. Якщо точка знаходиться у південній (західній) півкулі, то всі відповідні координати широти (довготи) вказано із знаком «–».

Вихідні дані
Файл riman2.res містить запис з точністю до 9 знаків після десяткової крапки відношення площ фіґур (меншої до більшої), на які контур поділяє поверхню Землі.

Приклад

Математична довідка
Площа сфери з радіусом r дорівнює 4πr².

Площа криволінійного трикутника, утвореного на цій сфері меншими дугами кіл з центром у центрі сфери, дорівнює (A + B + C – π) r², де
A, B, C — кути між дотичними до дуг, проведених у точці їх перетину,
π = 3,14159265358979323846… — число Піфагора — відношення довжини кола до його діаметра.

a є векторним добутком векторів b i c (позначают a = b × c), якщо:

• | a | = | b | · | c | · sin φ, де φ — кут між векторами b i c;
• a ⊥ b i a ⊥ c;
• трійка векторів a, b i c має додатну орієнтацію.

Для векторів b(b₁; b₂; b₃) і c(c₁; c₂; c₃) векторний добуток a = b × c має такі координати:

6. Гра «Ряд фішок», 36 балiв
Скiнченну кiлькiсть фiшок розташовано в ряд i вiдповiдним чином занумеровано послiдовними натуральними числами, починаючи з 1. Два гравцi по черзi забирають довiльнi одну або двi фiшки, розташованi поруч (номери яких вiдрiзняються на 1). Переможцем вважають того, хто:
(1) зробить останнiй хiд;
(2) примусить суперника зробити останнiй хiд.

Завдання
Створiть програму game.*, яка для довiльного варiанту гри (1) чи (2) i довiльної позицiї гри визначає всi виграшнi ходи — такi ходи, що ґарантують виграш (за умови правильного продовження гри зi свого боку) незалежно вiд ходiв суперника.

Вхідні дані
Файл game.in мiстить у вказаному порядку:

• число 1 або 2 — варiант гри;
• номери наявних фiшок, якi меншi за 18.

Вихідні дані
Перший i другий рядки файлу game.out мають мiстити в порядку зростання номери фiшок, забравши якi по однiй або разом з наступною по двi вiдповiдно гравець робить виграшний хiд з позицiї, заданої вхiдними даними. Якщо таких ходiв немає, то вiдповiдний рядок game.out порожнiй. Кожний непорожнiй рядок закiнчується одним пропуском i ознакою кiнця рядка.

Приклади