Veden mittaus

Sinulla on kaksi vesiastiaa (vasen ja oikea), joilla on tietyt tilavuudet. Tavoitteesi on mitata annettu määrä vettä astioiden avulla.

Astiat ovat aluksi tyhjiä. Joka askeleella saat täyttää tai tyhjentää jommankumman astian tai kaataa vettä astioiden välillä. Joka askeleella ainakin toisen astioista on täytyttävä tai tyhjennyttävä kokonaan.

Mikä on pienin mahdollinen siirrettävän veden kokonaismäärä, jolla saat mitattua halutun määrän vettä vasempaan astiaan?

Esimerkki: Vasemman astian tilavuus on 5 litraa, oikean astian tilavuus on 4 litraa ja vettä tulee mitata 2 litraa. Tässä tapauksessa pienin veden kokonaissiirtomäärä on 22 litraa. Yksi optimaalinen ratkaisu on seuraava:

1. Täytä vasen astia (vettä siirtyy 5 litraa)
2. Kaada vasemmasta astiasta oikea astia täyteen (vettä siirtyy 4 litraa)
3. Tyhjennä oikea astia (vettä siirtyy 4 litraa)`
4. Kaada vasemman astian sisältö oikeaan astiaan (vettä siirtyy 1 litraa)`
5. Täytä vasen astia (vettä siirtyy 5 litraa)`
6. Kaada vasemmasta astiasta oikea astia täyteen (vettä siirtyy 3 litraa)`

Toteuta tiedostoon water.py funktio min_amount, joka kertoo pienimmän mahdollisen siirrettävän veden kokonaismäärän.

Voit olettaa, että kummankin astian tilavuus on kokonaisluku välillä 1 \dots 500. Funktion tulee olla tehokas kaikissa tällaisissa tapauksissa. Jos mitään ratkaisua ei ole olemassa, haluttu vastaus on -1.

def min_amount(left_volume, right_volume, target):
    # TODO

if __name__ == "__main__":
    print(min_amount(5, 4, 2)) # 22
    print(min_amount(4, 3, 2)) # 16
    print(min_amount(3, 3, 1)) # -1
    print(min_amount(1, 1, 10**9)) # -1
    print(min_amount(10, 9, 8)) # 46
    print(min_amount(123, 456, 42)) # 10530