Вказівки
Дано два відра різного розміру та вказівку, яке з них наповнювати першим. Визначте, скільки дій потрібно, щоб відміряти точну кількість літрів, стратегічно переливаючи рідину між відрами.
Рішення має дотримуватися кількох правил:
- За раз можна виконати лише одну дію.
- Можливі лише 3 дії:
- Переливання з одного відра в інше, доки не станеться одне з двох:
a) перше відро спорожніє
b) друге відро наповниться вщерть
- Спорожнення відра без будь-яких дій з іншим.
- Наповнення відра без будь-яких дій з іншим.
- Після дії не можна опинитися в стані, коли стартове відро порожнє, а інше наповнене.
Програма приймає як вхідні дані:
- розмір першого відра
- розмір другого відра
- бажану кількість літрів, якої треба досягти
- яке відро наповнювати першим: перше чи друге
Програма має визначити:
- загальну кількість дій, потрібних, щоб досягти бажаної кількості літрів, включно з першим наповненням стартового відра
- у якому відрі врешті має опинитися бажана кількість літрів: у першому чи в другому
- скільки літрів залишиться в іншому відрі
Примітка: будь-яка зміна в одному чи обох відрах вважається однією (1) дією.
Приклад:
Перше відро вміщає до 7 літрів, а друге - до 11 літрів.
Нехай на певному кроці в першому відрі 7 літрів, а в другому 8 літрів (7,8).
Якщо спорожнити перше відро й нічого не робити з другим, отримавши відповідно 0 літрів і 8 літрів (0,8), це вважається однією дією.
Натомість, якби ми перелили з першого відра в друге, доки друге не наповнилося вщерть, і отримали 4 літри в першому відрі та 11 літрів у другому (4,11), це теж вважалося б лише однією дією.
Ще один приклад:
Перше відро вміщає 3 літри, а друге - до 5 літрів.
Нам сказано, що починати треба з першого відра.
Отже, перша дія - наповнити перше відро.
Другою дією ми вирішуємо спорожнити перше відро.
Третьою дією не можна наповнювати друге відро, бо це порушує третє правило: після жодної дії не можна опинитися в стані, коли стартове відро порожнє, а інше наповнене вщерть.
Написано з <3 у Fullstack Academy Ліндсі Левін.
Регістри
| Регістр |
Використання |
Тип |
Опис |
$a0 |
вхідні дані |
адреса |
масив слів з ємностями відер |
$a1 |
вхідні дані |
ціле число |
початкове відро (1 або 2) |
$a2 |
вхідні дані |
ціле число |
цільовий обʼєм |
$a3 |
вхідні/вихідні дані |
адреса |
масив слів з остаточним вмістом відер |
$v0 |
вихідні дані |
ціле число |
кількість потрібних дій, -1, якщо це неможливо |
$t0-9 |
тимчасовий |
будь-який |
використовується для тимчасового зберігання |
