1453: Переливання води


Submit solution


Points:10
Time limit:2.0s
Memory limit:64M
Author:

Problem types

Є двi посудини: в одну посудину помiщається a лiтрiв води, а в другу - b лiтрiв. Визначити мінімальну кількість кроків, необхідних для того, щоб в одній з посудин отримати c літрів води.

На початку обидві посудини порожні. Наступні операції вважаються "кроками":

  • спорожнення посудини,

  • заповнення посудини,

  • налити воду з однієї посудини в іншу, не розливаючи, поки одна з посудин не буде повна або порожня.

Формат вхідних даних

В окремих рядках мiстяться натуральнi числа a, b, c не бiльшi за 40000

Формат вихідних даних

Вивести мінімальну кількість кроків щоб отримати c літрів води або -1, якщо це неможливо

Приклад вхідних даних

5
2
3

Приклад вихідних даних

2

Приклад вхідних даних

2
3
4

Приклад вихідних даних

-1

Comments


  • 0
    bombocat
     commented on Feb. 20, 2021

    Задача досить цікава, дякую.

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

    1. Переливання від більшого до меньшого;
    2. Переливання від меньшого до більшого;
    3. Знайти де кількість кроків меньша та вивести на екран;

    Вдалого кодуваня :)


  • 0
    zvit
     commented on Nov. 21, 2019

    Час збільшено з 1 до 2 с. Повторно перевірено.