1. Банкiвська справа
Максимальна оцінка: 20 балів
Обмеження на час: 0,7 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: profit.in
Вихідний файл: profit.out
Програма: profit.*
Молодий ломбардець Гуччо Бальйон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ть програму, яка домоможе молодому ломбардцю отримати якнайбiльшi статки.
Вхідні дані
Перший рядок файлу у вказаному порядку м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дного файлу має м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лу).
Приклад
| profit.in | profit.out |
|---|---|
|
3 10 1 1 6 2 2 5 2 1 3 3 2 4 7 8 3 7 8 4 8 5 7 10 12 10 4 9 11 6 13 7 |
14 0 0 1 2 0 0 0 0 0 0 |
2. Опiр
Максимальна оцінка: 62 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: resistor.in
Вихідний файл: resistor.out
Програма: resistor.*
Сукупнiсть клем електричної схеми занумеровано натуральними числами в межах вiд 1 до n включно. Клеми з'єднано m опорами, величина кожного з яких в омах виражається невiд'ємним рацiональним числом.
Завдання
Створiть програму resistor.*, яка визначить опiр мiж клемами 1 i n.
Вхідні дані
Вхiдний файл resistor.in мiстить у вказаному порядку натуральнi числа n i m, розташовані у межах вiд 1 до 2500 включно, i далi m четвiрок невiд'ємних цiлих чисел: два номера клем, чисельник i знаменник величини опору в омах, що їх з'єднує.
Вихідні дані
Єдиний рядок вихiдного файлу resistor.out мiстить нескоротний дрiб — шуканий опiр в омах. Якщо знаменник дробу дорiвнює 1, то дробову риску / i сам знаменник не записувати. Якщо опiр нескiнчений, тобто немає послiдовностi опорiв, що сполучає клеми 1 i n, то файл resistor.out мiстить запис
Zero conductivity
Приклад
| resistor.in | resistor.out |
|---|---|
| 3 3 1 2 2 1 2 3 7 1 2 3 6 1 | 68/13 |
Примітка. Для розв'язання задачi непотрiбно подавати числа масивами цифр або розв'язувати систему лiнiйних рiвнянь з кiлькiстю змiнних, що перевищує 50.
Фізична довідка
Опір послідовного з'єднання дорівнює сумі величин сполучених опорів. Якщо у паралельному з'єднанні хоча б один з опорів дорівнює 0, то й опір всього з'єднання дорівнює 0. Інакше опір паралельного сполучення обернений до суми величин, обернених до сполучених опорів. У загальному випадку потрібно користуватися правилами Кіркгофа.
Алґебрична сума струмів у кожному вузлі розгалуження провідників (клеми), дорівнює 0 (струми, спрямовані у вузол, вважають додатними, спрямовані від вузла — від'ємними.
У будь-якому замкнутому контурі алґебрична сума падінь напруг дорівнює сумі електрорушійних сил у цьому контурі.
Для визначення опору складного ланцюга, описаного в умові задачі, потрібно провести уявний експеримент — приєднати до клем 1 і n джерело напруги E і визначити струми через всі опори:
скласти (n – 2) рівняння для клем на підставі 1-го правила Кіркгофа (рівняння, що залишаться, випливють із врахованих);
скласти (m – n + 2) рівняння для незалежних замкнених контурів на підставі 2-го правила Кіркгофа. Кожний з m опорів має війти в ці останні рівняння хоча б один раз;
розв'язати отриману систему лінійних рівнянь відносно невідомих струмів через дані опери, що пропорційні E;
опір системи знайти як відношення E до електричного струму, що проходить через джерело напруги.
При складанні рівнянь потрібно враховувати напрями струмів, які невідомі. Якщо розв'язок для якогось струму буде від'ємним, це означає, що його напрям протилежний до обраного.