Завдання ІІІ (міського) етапу 2004 року

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

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

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

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

Приклади

normal.datnormal.res
A<=>B(not A and not B) or (A and B)
A^B(not A and not B)

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

ABA and BA or BA=>BA <=> BA|BA^B
0 0 0 0 1 1 1 1
0 1 0 1 1 0 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 0 0

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

Функція Нормальна диз'юнктивна форма
A and B (A and B)
A or B (not A and B) or (A and not B) or (A and B)
A => B (not A and not B) or (not A and B) or (A and B)
A <=> B (not A and not B) or (A and B)
A|B (not A and not B) or (not A and B) or (A and not B)
A^B (not A and not B)

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».

Приклад

rectang.datrectang.res
2 3 2 5 3 7 3

0 0 1 1 2 0 2 0
0 0 2 0 5 0 1 1

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

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

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

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

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

Приклади

canon.datcanon.res
31


31
1024

210
2
84

22
2 *3*7

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

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

Вхідні дані
Перший рядок файла 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лькiсть ланок всiх маршрутiв не перевищує 7800.

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

Приклад

tax.intax.out
7 4 1 7 3
3 2 0 4 35 1 2 50 1 3 70 1
5 5 0 6 15 1 4 30 1 5 45 1
7 2 0 2 5 11 6 10 1 7 20 1
7 60 0 2 70 1 6 80 1 7 90 1
70 12
1510 2



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

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

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

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

Приклад

riman2.datriman2.res
90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 00.028571428

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

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

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

Для векторів b(b1; b2; b3) і c(c1; c2; c3) векторний добуток a = b × c має такі координати:

a1 = b2c3b3c2,
a2 = b3c1b1c3,
a3 = b1c2b2c1.

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стить у вказаному порядку:

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

Приклади

game.ingame.out
1 1 2 3 4


2
2 1 2 3 4

.
1 1 2 3

2

2 1 2 3


1 2
1 2 3 4 6 7 8 9

6 7 8 9
2 3