Завдання № 9
відбірково-тренувальних зборів
команди міста Києва

1. Лінійні рівняння

Завдання
Створiть програму linear.*, яка розв'яже систему n лiнiйних рiвнянь з цiлими коефiцiєнтами вiдносно m змiнних:

a11x1 + a12x2 + a13x3 + ⋯ + a1mxm = a1 (m + 1) ;
a21x1 + a22x2 + a23x3 + ⋯ + a2mxm = a2 (m + 1) ;
a31x1 + a32x2 + a33x3 + ⋯ + a3mxm = a3 (m + 1) ;

an1x1 + an2x2 + an3x3 + ⋯ + anmxm = an (m + 1) .

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

Для j в межах вiд 1 до n включно (j + 1)-ий рядок цього самого файлу мiстить послiдовнiсть цiлих коефiцiєнтiв ajk , роздiлених прогалинами, у порядку зростання k в межах вiд 1 до m + 1 включно.

Вiдомо, що (m + 1) n не перевищує 8000, а решта чисел вхiдного файлу не перевищують 1234567890 за модулем.

Вихідні дані

  1. Якщо система несумiсна, то єдиний рядок вихiдного файлу linear.out має мiстити з першої позиції запис: «No solution»

  2. Якщо розв'язок системи єдиний, то єдиний вихiдного файлу linear.out має мiстити xj в порядку зростання j в межах вiд 1 до m включно.

  3. Якщо розв'язкiв системи безлiч, то j-ий рядок вихiдного файлу linear.out має мiстити коефiцiєнти j-го рiвняння системи, отриманої в результатi застосування методу послiдовного виключення змiнних — всього (m + 1) число.

У випадках 2–3 рядок вихідного файлу починається одним пропуском, далі йде запис першого числа, пропуск, запис другого числа, пропуск і т.д. Усi числа потрiбно подати нескоротним дробом (чисельник цiлий, знаменник натуральний, якщо знаменник дорiвнює 1, то дробову риску / i знаменник не вказувати). Для розв'язання задачi непотрiбно подавати цiлi числа масивами їхнiх цифр.

Приклади

linear.inlinear.out
2 2
3 4 5
6 8 9
Система несумісна!


2 2
3 4 5
4 4 1
-4 17/4


2 2
6 8 10
9 12 15
1 4/3 5/3


Примітка щодо оцінювання
Бали за запис «No solution» (тести 17–20) присуджують лише тоді, коли є правильна відповідь хоча б на один тест 1–16.

2. Хімія

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

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

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

Приклад

chemie.inchemie.out
Вa(OH) +HCl=BaCl +H O
      2         2  2
Ba(OH) +2HCl=BaCl +2H O
      2          2   2