Smålänningen Ingmar Krampvad trodde sig ha insett hur han
lätt kunde tjäna en krona eller två på dagens snabba
valutafluktuationer. Ingmar växlade 300:- till dollar (kurs 8,00) och
fick då 37,50 dollar. Dessa 37,50 dollar växlade han sedan till
D-mark (kurs 0,60) och fick då 62,50 D-mark. Slutligen växlade
Ingmar tillbaka D-marken till kronor (kurs 0,20) och fick då 312,50:-.
Ingmar var överlycklig över att ha gjort en vinst på 12,50:-!
Tyvärr blev han snabbt nedtagen på jorden av personalen på
Kenobanken när de gav honom räkningen på växlingscourtagen
på 60:- (2% på transaktionsbeloppet, dock minst 20:- per transaktion).
Ingmars idé hade dock fungerat om banken inte hade tagit ut någon
växlingsavgift (vilket tyvärr är en utopi...).
Uppgiften är alltså att skriva ett program som avgör om
det går att göra en växlingsvinst, eller ej, hos en bank,
under förutsättning att banken inte tar ut några avgifter
för transaktionerna. Alla ingående valutatransaktioner i ett
växlingsförsök sker i bankens dator. Detta för att undvika
de avrundningsfel som kunde uppstått om banken hade varit tvungen
att ge Ingmar riktiga sedlar efter varje deltransaktion.
Indata:
Första raden anger antalet testfall programmet skall behandla (N).
Därefter följer de N testfallen. Första raden i varje testfall
anger antalet växlingskurser (M<1000). Följande M rader beskriver
de möjliga växlingskurserna, med en kurs per rad. Varje kursrad
innehåller två valutor (tre versaler från det engelska
alfabetet) och kursen mellan dem. Det finns exakt ett blanktecken mellan
de tre ingående delarna. Ex. SEK USD 8.00 betyder att det går
8,00 SEK på en USD (men det betyder inte att det går att växla
USD till SEK!). Varje testfall avslutas med en rad som anger startvalutan
(=slutvalutan) för växlingsförsöket.
Utdata:
Skall bestå av N rader, en för varje testfall med texten 'Possible'om
det är möjligt att växla till sig en vinst, eller texten
'Impossible', om det inte går. OBS! Testdata är valda så
att datorns avrundningsfel inte skall ställa till några tveksamheter.
Exempel:
Indata:
2 3 SEK USD 8.00 USD DEM 0.60 DEM SEK 0.20 SEK 4 SEK USD 8.00 USD DEM 0.60 SEK DEM 5.00 DEM USD 1.60 SEK
Utdata:
Possible Impossible