Sinulla on vesiastiat, joiden tilavuudet ovat a ja b litraa, ja tavoitteesi on mitata x litraa vettä astioiden avulla.

Astiat ovat aluksi tyhjiä, eikä niissä ole mitta-asteikkoa. Joka askeleella saat täyttää tai tyhjentää jommankumman astian tai kaataa vettä astioiden välillä. Kuitenkin joka askeleella ainakin toisen astioista on täytyttävä tai tyhjennyttävä kokonaan, koska muuten mittaus ei olisi tarkka.

Mikä on pienin mahdollinen siirrettävän veden kokonaismäärä, jolla saat mitattua x litraa vettä ensimmäiseen astiaan? Esimerkiksi kun a=5, b=4 ja x=2, pienin siirtomäärä on 22 litraa. Tässä on yksi optimaalinen ratkaisu:

1. Täytä ensimmäinen astia (vettä siirtyy 5 litraa)
2. Kaada ensimmäisestä astiasta toinen astia täyteen (vettä siirtyy 4 litraa)
3. Tyhjennä toinen astia (vettä siirtyy 4 litraa)`
4. Kaada ensimmäisen astian sisältö toiseen astiaan (vettä siirtyy 1 litraa)`
5. Täytä ensimmäinen astia (vettä siirtyy 5 litraa)`
6. Kaada ensimmäisestä astiasta toinen astia täyteen (vettä siirtyy 3 litraa)`

Voit olettaa, että 1 \le a,b \le 500 ja 1 \le x \le a. Jos mitään ratkaisua ei ole olemassa, haluttu vastaus on -1.

Python

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

def count(a,b,x):
    # TODO

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

Java

Toteuta tiedostoon Water.java metodi count, joka kertoo pienimmän mahdollisen siirrettävän veden kokonaismäärän.

import java.util.*;

public class Water {
    public int count(int a, int b, int x) {
        // TODO
    }

    public static void main(String[] args) {
        Water w = new Water();
        System.out.println(w.count(5,4,2)); // 22
        System.out.println(w.count(4,3,2)); // 16
        System.out.println(w.count(3,3,1)); // -1
        System.out.println(w.count(10,9,8)); // 46
        System.out.println(w.count(123,456,42)); // 10530
    }
}