1. Банкiвська справа (20 балiв)
Молодий ломбардець Гуччо Бальйонi (герой серiї творiв французького письменника Морiса Дрюона) часто виконував таємнi доручення сучасних йому можновладцiв Францiї, Анґлiї та Італiї. Не маючи можливостi протягом трьох рокiв безпосередньо самому займатися справами, вiн вирiшив отримати зиск, вклавши грошi у справи паризьких банкiрiв. Виявилося, що розмiр винагороди (% зиску) рiзний у рiзних банкiрiв. Звичайно, чим бiльшу суму вiн дасть банкiру, тим бiльше отримає через 3 роки. І не менше, нiж дав банкiру. Але в кожного банкiра % зиску рiзний для рiзних сум. Нажаль, за розрахунками Гуччо, йому нiколи не отримати бiльше ніж 1000 лiврiв (середньовiчних французьких монет).

Завдання
Створiть програму profit.*, яка домоможе молодому ломбардцю отримати якнайбiльшi статки.

Вхідні дані
Перший рядок файлу profit.dat у вказаному порядку мiстить 2 натуральних числа:
m — кiлькiсть лiврiв, яку молодий Гуччо може використати для збагачення;
n — кiлькiсть паризьких банкiрiв.
Тут m і n не перевищують 100.
Для j в межах вiд 1 до m (j + 1)-ий рядок цього файлу мiстить послiдовнiсть n натуральних чисел. k-ий член цiєї послiдовностi — це кiлькiсть монет, яку отримає Гуччо через три роки вiд k-го банкiра, вiддавши йому j монет перед вiд'їздом.

Вихідні дані
Перший рядок вихiдного файлу profit.res має мiстити найбiльшу кiлькiсть лiврiв, яку може мати молодий ломбардець через 3 роки, використавши m лiврiв належним чином.
Другий рядок цього файлу має мiстити послiдовнiсть n невiд'ємних цiлих чисел. k-ий член цiєї послiдовностi — це кiлькiсть лiврiв, яку має дати Гуччо k-му банкiру, щоб отримати максимальний зиск вiд своїх капiталовкладень (потрiбно подати хоча б один з варiантiв розподiлу).

Приклад

2. Оп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 до електричного струму, що проходить через джерело напруги.

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

3. Регулярні многогранники (29 балів)
Регулярним (опуклим) многогранником називають (опуклий) многогранник, у якому всі грані — правильні многокутники, а многогранні кути при всіх вершинах однакові. Інакше кажучи, грані кожного виду зустрічаються в тій самій кількості й у тій самій послідовності при обході навколо кожної вершини. Для таких многогранників, як і для всіх опуклих многогранників, справджується теорема Ейлера: g – e + v = 2. Тут g — кількість всіх граней, e — кількість всіх ребер, v — кількість всіх вершин многогранника.

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

Вхідні дані
Перший рядок файлу regular.dat містить у вказаному порядку g і e — відповідно кількості всіх граней і ребер, що менші за 200. Для всіх вхідних даних тестування не існує регулярних многогранників, у яких кількість сторін грані перевищує 10.
Другий і наступні рядки містять довільне за формою повідомлення українською мовою щодо відповіді. Це зроблено для полегшення процесу перевірки коректності тестів членами журі та учасниками олімпіади. Зображення моделей можна знайти, наприклад, у такій монографії: М.Веннинджер, «Модели многогранников», М.: Мир, 1974, 236 с. Опрацювання другого рядка файлу вхідних даних програмою учасника не передбачено.

Вихідні дані
Кожний рядок файлу regular.res має містити невід'ємні цілі числа, що є відповідно кількостями 3-, 4-, 5-, 6-, 7-, 8-, 9- чи 10-кутних граней певного регулярного многогранника. Рядки цього файлу потрібно впорядкувати у лексикографічному порядку (за числами).

Приклад