3.1. Банківська справа (динамічне програмування)

Запровадимо такі позначення:
a_jk — кількість монет, які герой отримає за j монет від банкіра k (вхідні дані);
b_jk — найбільша кількість монет, які герой отримає при найоптимальнішому розподілі j монет серед банкірів 1, 2, …, k.

Покладемо: a_0k = b_0k = 0.

Маємо:
b_j1 = a_j1 при j = 1, 2, …, m;
b_{j (k + 1)} = max { b_{(j – l) k} + a_{l (k + 1)} }_{l = 0, 1, 2, …, j} при k = 1, 2, …, n – 1.

Те l, при якому досягається максимум, потрібно запам'ятати як елемент таблиці с_j (k + 1), щоб потім скористатися при знаходженні оптимального розподіду монет на основі таких тверджень:

• якщо b_jk < b_{j (k + 1)}, то при оптимальному розподілі j монет серед банкірів 1, 2, …, (k + 1) потрібно обов'язково скористатися послугами банкіра (k + 1);

• якщо b_jk = b_{j (k + 1)}, то при оптимальному розподілі j монет серед банкірів 1, 2, …, (k + 1) можна обійтися без послуг банкіра (k + 1).

3.2. Опір (графи + лінійна алгебра)

Дії припиняти одразу після визначення й запису відповіді:

1. Агрегувати систему, тобто замінити одним опором послідовне чи паралельне сполучення опорів, вилучення петель (обидва кінці дроту приєднано до одного опору), вилучення з розгляду опорів з ізольованим кінцем (приєднаного до клеми, до якої не приєднано жодного іншого опору).

2. Встановити, чи після приєднання джерела напруги до клем 1 і n потече струм лише по одному провіднику? Якщо відповідь ствердна, то шуканий опір дорівнює опору цього провідника. Якщо не буде жодного провідника, сполученого з клемою 1, або не буде жодного провідника, сполученого з клемою n, то провідність між клемами 1 і n дорівнює нулю.

3. Встановити (наприклад, «пошуком вшир») можливість сполучення клем 1 і n послідовністю нульових опорів. Якщо це можливо, то шуканий опір дорівнює нулю.

4. Встановити (наприклад, «пошуком вшир») можливість сполучення клем 1 і n послідовністю довільних опорів. Якщо це неможливо, то провідність між клемами 1 і n дорівнює нулю.

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

   • знайти найкоротший (за кількістю ланок) маршрут, що сполучає клеми 1 і n. Вільний член відповідного рівняння дорівнює 1, що відповідає приєднанню джерела напруги 1 V;

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

6. Розв'язати систему лінійних рівнянь за допомогою алґоритму Гауса (послідовним вилученням змінних) з урахуванням правил арифметичних дій з раціональними числами.

7. Знайти суми величин струмів, що виходять з клеми 1.

Правило «пошуку вшир» на графі: множина вершин, які можна досягнути з певної вершини k, подолавши m + 1 ребро (дугу) — це множина всіх тих вершин, які можна досягнути, подолавши одне ребро (дугу) з тих вершин, для досягнення яких з k-ої вершини потрібно подолати m ребер (дуг).