1. Хімія, 20 балів

Завдання
Створіть програму chemie.*, яка:

• визначить найменші натуральні коефіцієнти, які не перевищують 30, і які потрібно написати перед формулою кожної речовини (у результаті хімічної реакції кількість атомів будь-якого хімічного елемента стала);

• запише правильно складене рівняння хімічної реакції.

Вхідні дані
Файл chemie.dat містить формули субстратів хімічної реакції, розділені знаком + і записані ліворуч від знаку =, і продуктів цієї ж реакції, розділені знаком + і записані праворуч від знаку =. Кількість всіх речовин (субстратів і продуктів) не перевищує 10. Позначення всіх хімічних елементів (1-ий рядок файлу) починаються з великих літер латиниці. Більшу за 1 кількість атомів хімічного елемента у сполуці вказано знизу праворуч (2-ий рядок файлу). В одній формулі позначення одного й того самого елемента може зустрічатися не один раз. Якщо сполука містить кілька однакових ґруп атомів, то у хімічній формулі відповідний запис виділяють круглими дужками, а кількість повторень вказано праворуч знизу від правої круглої дужки. Прогалини у першому рядку зустрічаються лише над числами другого рядка, але перший рядок не закінчується прогалинами. Вхідні дані ґарантують існування і єдиність розв'язку.

Вихідні дані
Файл chemie.res отримують вставлянням у перший рядок коефіцієнтів, відмінних від 1, і відповідної кількості пропусків у другий рядок під цими коефіцієнтами.

Приклад

Вa(OH) +HCl=BaCl +H O
      2         2  2

Ba(OH) +2HCl=BaCl +2H O
      2          2   2

2. Многоґранник, 20 балів

Вхідні дані
Перший рядок вхідного файлу solid.dat містить натуральне число n — кількість вершин многоґранника, поверхню якого можна неперервно і взаємно однозначно відобразити на сферу. Для j в межах від 1 до n включно (j + 1)-ий рядок цього файлу містить у порядку зростання номери вершин, які з'єднані з j-ою вершиною ребрами. Відомо, що:

• вершин не більше, ніж 2000;
• ребер не більше, ніж 4000;
• лише в одній ґрані кількість ребер перевищує 8.

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

• єдиний рядок вихідного файлу solid.res міститиме у вказаному порядку невід'ємні натуральні числа n₃, n₄, …, n_m — кількості 3-, 4-, …, m-кутних ґраней відповідно, де m — найбільша кількість вершин однієї ґрані многокутника;

• файл l.res міститиме n_l рядків;

• кожний рядок вихідного файлу l.res міститиме натуральні числа i₁, i₂, …, i₁ — перелік номерів вершин l-кутної ґрані у порядку обходу її за периметром, причому різним ґраням відповідатимуть різні рядки, а зі збільшенням номера рядка величина (i₁n² + i₂n + i₃) зростатиме (лексикографічний порядок).

3. Приватні інтереси, 20 балів
На клітинках прямокутної таблиці, що має m рядків та n стовпчиків, розкладено монети. Двоє гравців по черзі рухають пішак або праворуч, або вгору на одне поле за один хід. Гру розпочинає перший гравець з крайнього нижнього лівого поля. Гру припиняють після досягнення пішаком першого (якщо рахувати згори вниз) рядка чи останнього (якщо рахувати зліва направо) стовпчика таблиці. Кожен гравець:

• не має можливості спілкуватися з суперником;
• знає розподіл монет перед початком гри;
• знає розташування пішака у будь-який момент гри;
• забирає монети з клітин, на які ставить пішак;
• намагається отримати найбільшу суму грошей за всю гру;
• ходить праворуч лише тоді, коли хід вгору приносить менший остаточний зиск;
• знає і враховує намагання суперника;
• знає, що суперник діє аналогічно.

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

Вхідні дані
Перший рядок файлу privat.dat містить у вказаному порядку натуральні числа m та n.

Для j в межах від 1 до m включно (j + 1)-ий рядок цього ж файлу містить невід'ємні цілі числа — сукупні вартості монет у клітинках j-го рядка таблиці в тому порядку, як вони (клітинки цього рядка) розташовані в таблиці зліва направо. Кількість всіх чисел файлу не перевищує 12346, максимальний виграш не перевищує 65432 (золотих).

Вихідні дані
Перший рядок вихідного файлу privat.res має містити два невід'ємних цілих числа — виграші (кількості зібраних монет) першого та другого гравців відповідно.

Другий рядок цього самого файлу має містити послідовність символів, що описують напрям ходів пішака (від першого до останнього) для досягнення цього результату: u — вгору (від анґлійського up), r — праворуч (від анґлійського right).

Приклад

4. Вечірка, 24 бали.

Завдання
Створіть програму party.*, яка допоможе встановити, як розсілися за круглим столом студенти (обличчям до центру столу) й фах кожного з учасників вечірки.

Вхідні дані
Кожен рядок файлу party.dat складається з 3-х частин, розділених пропусками:

• ім'я або фах учасника вечірки;

• cимвол для позначення його розташування відносно того учасника вечірки, ім'я або фах якого вказані наприкінці твердження:

  • < — читати «ліворуч від»;
  • > — читати «праворуч від»;
  • | — читати «навпроти»;

• ім'я або фах учасника вечірки.

Всі рядки, крім останнього, закінчуються комою, а останній — крапкою. Всі літери у словах файлу малі, крім перших літер імен. Апостроф не використано. Кількість учасників вечірки, кількість літер у кожному слові та кількість рядків файлу не перевищують 25. Імена та фахи всіх учасників перераховано у файлі party.dat. Всі слова — у називному відмінку. Всі імена та фахи — різні.



Вихідні дані
Кожний рядок файлу party.res має містити по одному, відмінному від інших, варіанту розташування студентів за столом, який не суперечить умові задачі і вхідним даним. Потрібно вказати імена учасників вечірки у порядку обходу столу проти руху годинникової стрілки, якщо дивитися згори: кожний наступний учасник сидить праворуч від попереднього. Починати перелік потрібно з імені студента, яке буде першим у списку імен, впорядкованих у алфавітному порядку української абетки: А Б В Г Ґ Д Е Є Ж З И І Ї Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ю Я. Після кожного імені (через пропуск) потрібно вказати в дужках фах студента. Ім'я кожного наступного учасника потрібно відділити комою і пропуском, а в кінці рядка поставити крапку. Всі слова — у називному відмінку.

Приклад

філолог | Кирило,
Кирило < історик,
біолог > Віталій,
Федір > Євген,
хімік > Федір.

Віталій (хімік), Кирило (біолог), Євген (історик), Федір (філолог).

5. Багатокутник, 12 балів

Завдання
Створіть програму polygon.*, яка:

• зображує сторони рівностороннього трикутника (білі на чорному тлі, одна сторона — горизонтальна і розташована знизу);

• після натискання клавіші Enter кожний відрізок попереднього рисунку ділиться на 3 однакових частини, середня частина замінюється ламаною з двох ланок тієї самої довжини, причому нова вершина ламаної лежить зовні області, обмеженої ламаною попереднього зображення. Зображення має максимальні розміри (на весь екран).

Після 6-го натискання клавіші Enter програма припиняє роботу.

6. Корiнь квадратний, 34 бали
Щоб добути квадратний корiнь з десяткового дробу (наприклад, 65432.109), його запис розбивають праворуч i лiворуч вiд десяткової крапки на гранi, що мiстять по 2 цифри. У крайнiй лiвiй гранi може виявитися i одна цифра (6). Перша цифра кореня (2) знаходиться як найбiльша з усiх тих цифр, квадрати яких не перевищують першої гранi (6). Потiм вiд першої гранi вiднiмають квадрат першої цифри кореня (4), i до рiзницi приписують праворуч (зносять) наступну грань (54). Лiворуч вiд отриманого числа (254) пишуть подвоєну першу цифру кореня (4), а за наступну цифру (5) беруть найбiльшу з тих, добуток яких на число, утворене приписуванням її до подвоєної першої цифри праворуч, (45 ∙ 5=225) не перевищує результату приписування до попередньої рiзницi вiдповiдної гранi (254). Цю цифру (5) записують пiсля першої цифри кореня i т.д. Десяткова крапка у коренi ставиться тодi, коли зноситься перша грань праворуч вiд десяткової крапки числа.

Завдання
Створiть програму root.*, яка вираховує корiнь квадратний додатного десяткового дробу.

Вхідні дані
Єдиний рядок вхiдного файлу root.dat мiстить у вказаному порядку скiнченний або перiодичний додатний десятковий дрiб (всього — до 1000 символiв разом з десятковою крапкою) a та натуральне число n, яке не перевищує 100.

Вихідні дані
Єдиний рядок файлу root.res має мiстити подання кореня квадратного а скiнченним чи перiодичним десятковим дробом, якщо це можливо, iнакше — корiнь квадратний числа a з недостачею з точнiстю до n цифр пiсля десяткової крапки.

Приклади