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