Az S. 48. feladat (2009. november)

S. 48. Adott néhány, kezdetben színültig töltött, ismert térfogatú edény. Egy lépésben az alábbiak egyikét tehetjük:

- egy edény teljes tartalmát kiöntjük,

- egy edényt újra színültig töltünk (akárhány alkalommal),

- egy edényből annyit töltünk át egy másik edénybe, hogy utóbbi színültig megteljen,

- egy edényből annyit töltünk át egy másik edénybe, hogy előbbi kiürüljön (de az utóbbi nem csordulhat túl).

Írjunk programot, mely meghatározza, hogy a fenti lépések ismétlésével -- tehát pontosan -- kimérhető-e, és ha igen, hogyan egy kívánt folyadékmennyiség. A program az adatokat a standard bemenetről olvassa, az eredményt a standard kimenetre írja.

A bemenet első sorában két, szóközzel elválasztott egész szám, az edények 2N4 száma, illetve a kimérendő 1V30 folyadékmennyiség szerepel. Az ezt követő N sorban rendre egy-egy egész szám áll, az (i+1)-edik sorban az i-edik edény 1C_i30 űrtartalma.

A kimenet első sorába, ha a kívánt folyadékmennyiség előállítható valamelyik edényben, akkor az ehhez minimálisan szükséges L lépések száma, egyébként ,,-1'' kerüljön. Ha a folyadékmennyiség kimérhető, akkor az ezt követő L sor mindegyike két, szóközzel elválasztott számot tartalmazzon: az első számérték a forrásedény, a második a céledény sorszáma, illetve szám helyett ,,*'' karakter, ha az első vagy második típusú lépést végeztük. (A ,,*'' karakter lényegében egy végtelen kapacitású edényt szimbolizál.) Több megoldás esetén bármelyik megadható.

Beküldendő a feladat megoldását tartalmazó forrás és projektállományok (az s48.exe és más, a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét bemutató dokumentáció egy tömörített mappában (s48.zip).

A kiadott tesztesetek be- és kimenetei letölthetőek innen.

(10 pont)

A beküldési határidő 2009. december 10-én LEJÁRT.

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Éles András, Élő Dániel, Fehér Péter, Kovács 125 András, Nagy 111 Miklós.
9 pontot kapott:	Borsos 607 Zalán, Weisz Ágoston.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.

A KöMaL 2009. novemberi informatika feladatai