Feladat: S.48 Korcsoport: - Nehézségi fok: -
Füzet: 2009/november, 490. oldal  PDF file
Témakör(ök): Nehezebb feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

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 1Ci30 ű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).