Az alkimisták kísérletei, hogy ólomból aranyat csináljanak, évszázadokon át meghiúsult. Az utolsó Alkímista Klub Találkozón (Alchemist Club Meeting - ACM) szenzációs áttörés történt. Három vegyszer, az Algolene, Basicine és a Cobolase megfelelő arányú keverésével készített elegy az ólomból aranyat csinál. Azóta Algolene, Basicine és a Cobolase (röviden A, B, C) általában nem árulják egyenként , hanem csak a keverésükkel készített vegyület vásárolható meg.
Tekintsük a következő példát! Két vegyület kapható Algolene, Basicine és a Cobolase-ből, 1:2:3 és 3:7:1 keverési arányú. A vegyületek 1:2 arányú keverésével az A, B, C-ből álló keverék 7:16:5 arányú lesz. De nincs mód kombinálni a keverékeket, oly módon, hogy 3:4:5 arány legyen a végeredmény. Ha van egy 2:1:2 arányú keverékünk is, akkor a 3:4:5 keverési arány előállítható 8 rész 1:2:3, 1 rész 3:7:1 és 5 rész 2:1:2 arányú keverékből.
Határozd meg, hogy melyik keverék állítható elő a megadott arányú keverékekből, lehetőség szerint minimális mennyiségű alapanyagból. Írj programot, amely meghatározza a keverési arányokat!
Bemenet:
A bemeneti állomány néhány tesztesetet tartalmaz. Minden teszteset első sorában egy n egész szám van (0 <= n < 100), amely megadja, hogy hány keveréket használunk az adott esetben. A következő n sor három nem negatív egészet (ai, bi, ci) tartalmaz, amelyek az A, B, C vegyületek keverési arányát jelentik az i-ik vegyületnél. Legkevesebb egy összetevő pozitív minden vegyületnél. Végül egy sorban három nem negatív egész (a, b, c) található, amelyek megadják a vegyületek keverési arányát a készítendő vegyületben. Legalább egy szám pozitív. Az input állomány a tesztesethez tartozó vegyületek számát mutató sorbeli nullával zárul.
Kimenet:
Minden tesztesetnél a "Mixture" szót kell kiírni, valamint a teszteset számát. A következő sorba a "Possible" illetve az "Impossible" szót kell írni, attól függően, hogy a kívánt vegyület kikeverhető-e vagy sem.
Példa:
|
INPUT.TXT |
OUTPUT.TXT |
|
2
|
Mixture 1 Impossible Mixture 2 Possible |
(ACM döntő 1998)