1. Трикутник Рело, 16 балів
Трикутник Рело — опукла фіґура, обмежена трьома дугами по 60° кіл з однаковими радіусами a.

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

• зчитає з клавіатури у вказаному порядку одноцифрове натуральне число k і дійсне число t в межах від 0.1 до 10;

• зобразить в центрі екрану на чорному тлі на весь екран монітора трикутник Рело жовтого кольору (тут і надалі колір фіґури — це колір контура фіґури і її внутрішніх точок), розташований всередині світло-синього квадрата з довжиною сторони a, причому одна з вершин трикутника Рело — середина верхньої сторони квадрата. Всередині трикутника розташовано червоний круг з центром у точці, рівновіддаленій від вершин трикутника, радіус якого (круга) дорівнює a/10;

• після натискання клавіші Enter покаже покадрову зміну кожні t секунд зображення, при якому трикутник Рело повертається проти руху годинникової стрілки на сталий кут 30°/k, не виходячи за межі нерухомого квадрата. При цьому центр червоного круга весь час рівновіддалений від вершин трикутника Рело;

• припинить роботу після натискання будь-якої клавіші.

Наприклад, при введенні чисел

2 1

трикутник Рело буде повертатися на 15° щосекунди.

2. Послідовність, 12 балів
За допомогою таблиці задано перші 18 членів послідовності цілих чисел a_n.

Наступні члени цієї послідовності задано такими рівностями:
a _3n = a_n,
a_{1 + 9n} = 2a_{2 + 3n} – a_{1 + 3n},
a_{2 + 9n} = 5a_{2 + 3n} – 4a_{1 + 3n},
a_{4 + 9n} = 3a_{2 + 3n} – 2a_{1 + 3n},
a_{5 + 9n} = 6a_{2 + 3n} – 5a_{1 + 3n},
a_{7 + 9n} = 4a_{2 + 3n} – 3a_{1 + 3n},
a_{8 + 9n} = 7a_{2 + 3n} – 6a_{1 + 3n}.

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

Вхідні дані
Файл sequence.dat містить лише натуральне число n, яке має не більше, ніж 100 цифр.

Вихідні дані
Файл sequence.res має містити лише a_n.

Приклад

3. Множники, 12 балів

Завдання
Створіть програму factor.*, яка розкладе многочлен з цілими коефіцієнтами на множники — многочлени з цілими коефіцієнтами, що вже неможливо розкласти на множники-двочлени з цілими коефіцієнтами. Розв'язання задачі не вимагає подання чисел масивами їхніх цифр, якщо на зберігання цілих чисел відведено 4 байти.

Вхідні дані
Вхідний файл factor.dat містить у вказаному порядку натуральне число n — степінь многочлена й (n + 1) ціле число — коефіцієнти многочлена в порядку спадання степеня від n до 0 включно, n < 100.

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

Кожний наступний рядок цього самого файлу містить у вказаному порядку такі цілі числа:

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

Починаючи з другого рядка factor.res, із зростанням номера рядка, третє число (старший коефіцієнт двочлена) не спадає. Для двочленів-дільників з однаковим старшим коефіцієнтом спочатку записуються дані про двочлен меншого степеня. Для двочленів-дільників одного степеня з однаковим старшим коефіцієнтом спочатку записуються дані про двочлен з від'ємним вільним членом (останнє число рядка). Дані про дільник многочлена, що не є двочленом (остача від ділення многочлена на всі його дільники-двочлени, враховуючи їх кратність), записують у останньому рядку.

Кожне число файлу factor.res має не більше двох цифр.

Приклад

Математична довідка
Якщо нескоротний дріб p/q є коренем многочлена змінної x з цілими коефіцієнтами, то:

• p — дільник вільного члена;
• q — дільник старшого коефіцієнта;
• многочлен ділиться без остачі на лінійний двочлен (qx – p), а коефіцієнти частки — цілі.

4. Спільний елемент, 15 балів

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

Вхідні дані
Файл common.dat містить (2n + 1) невід'ємне ціле число. Перше число — n. В j-ій парі чисел після n (у вказаному порядку) — перший член j-ої проґресії та її різниця. Всі числа вхідного файлу не перевищують 10000, причому n < 100.

Вихідні дані
Файл common.res має містити лише шукане число. Якщо такого числа немає, то файл містить 0.

Приклад

Математична довідка
Найбільший спільний дільник двох натуральних чисел — це найменше натуральне число, яке можна подати лінійною комбінацією даних чисел з цілими коефіцієнтами:

Всі такі лінійні комбінації ax + by кратні НСД(a, b).

5. Шашка на кубі, 14 балів
Поверхню куба відрізками, паралельними до ребер куба, поділено на квадратні клітини, довжина сторін яких у l (непарне натуральне число) разів менша за довжину ребра куба. Шашку пересувають за один хід з клітини на довільну суміжну з нею (що має з даною спільну сторону).

Завдання
Створіть програму draught.*, яка обчислить, скількома різними способами може шашка потрапити за m ходів з клітини в центрі однієї ґрані на клітину, розташовану в центрі суміжної ґрані.

Вхідні дані
Вхідний файл draught.dat містить натуральні числа l та m, де l < 52, m < 200.

Вихідні дані
Вихідний файл draught.res має містити ціле число — шукану кількість способів.

Приклад

6. Опiр, 31 бал
Сукупнiсть клем електричної схеми занумеровано натуральними числами в межах вiд 1 до n включно. Клеми з'єднано m опорами, величина кожного з яких в омах виражається невiд'ємним рацiональним числом.

Завдання
Створiть програму resistor.*, яка визначить опiр мiж клемами 1 i n.

Вхідні дані
Вхiдний файл resistor.dat мiстить у вказаному порядку натуральнi числа n i m, розташовані у межах вiд 1 до 2500 включно, i далi m четвiрок невiд'ємних цiлих чисел: два номера клем, чисельник i знаменник величини опору в омах, що їх з'єднує.

Вихідні дані
Єдиний рядок вихiдного файлу resistor.res мiстить нескоротний дрiб — шуканий опiр в омах. Якщо знаменник дробу дорiвнює 1, то дробову риску / i сам знаменник не записувати. Якщо опiр нескiнчений, тобто немає послiдовностi опорiв, що сполучає клеми 1 i n, то файл RESISTOR.RES мiстить запис

Zero conductivity

Приклад

Примітка. Для розв'язання задачi непотрiбно подавати числа масивами цифр або розв'язувати систему лiнiйних рiвнянь з кiлькiстю змiнних, що перевищує 50.

Фізична довідка
Опір послідовного з'єднання дорівнює сумі величин сполучених опорів. Якщо у паралельному з'єднанні хоча б один з опорів дорівнює 0, то й опір всього з'єднання дорівнює 0. Інакше опір паралельного сполучення обернений до суми величин, обернених до сполучених опорів. У загальному випадку потрібно користуватися правилами Кіркгофа.

1. Алґебрична сума струмів у кожному вузлі розгалуження провідників (клеми), дорівнює 0 (струми, спрямовані у вузол, вважають додатними, спрямовані від вузла — від'ємними.

2. У будь-якому замкнутому контурі алґебрична сума падінь напруг дорівнює сумі електрорушійних сил у цьому контурі.

Для визначення опору складного ланцюга, описаного в умові задачі, потрібно провести уявний експеримент — приєднати до клем 1 і n джерело напруги E і визначити струми через всі опори:

• скласти (n – 2) рівняння для клем на підставі 1-го правила Кіркгофа (рівняння, що залишаться, випливють із врахованих);

• скласти (m – n + 2) рівняння для незалежних замкнених контурів на підставі 2-го правила Кіркгофа. Кожний з m опорів має війти в ці останні рівняння хоча б один раз;

• розв'язати отриману систему лінійних рівнянь відносно невідомих струмів через дані опери, що пропорційні E;

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

При складанні рівнянь потрібно враховувати напрями струмів, які невідомі. Якщо розв'язок для якогось струму буде від'ємним, це означає, що його напрям протилежний до обраного.