Közép-európai Informatikai Olimpia 1999

Egy raktárban, amely több épületből áll, úgy tárolják az árukat, hogy egy épületben csak egyfajta árut tárolnak. Minden árufajta egy cimkét kapott, ami az angol ábécé egy kisbetűje. A raktáros szállítási rendeléseket fogad, amelyeket a beérkezésük sorrendjében teljesít. Minden rendelés csak egy árura vonatkozhat. A másnapra vonatkozó rendeléseket összegyűjtötték, de a sorrend összekeveredett.
Az a feladat, hogy kiszámítsuk az összes lehetséges sorrendet.

Bemenet:

Az ORDERS.IN állomány egyetlen sora az összekeveredett rendeléssorrendet tartalmazza. Minden rendelés egy kisbetű. A rendelések száma nem haladja meg a 200-at.

Kimenet:

Az ORDERS.OUT állományba kell írni az összes lehetséges rendeléssorrendet (ismétlés nélkül), amiből az input összekeveredéssel keletkezhetett. Az egyes lehetséges rendeléssorrendeket ábécé sorrendben kell külön sorba írni. A lehetséges output legfeljebb 2 Mbyte.

Példa:
 

ORDERS.IN	ORDERS.OUT
bbjd	bbdj  bbjd  bdbj  bdjb  bjbd  bjdb  dbbj  dbjb  djbb  jbbd  jbdb  jdbb

Manapság a telefonszámok egyre hosszabbak lesznek, így nehéz megjegyezni őket. Ezért betűket is használhatunk számok helyett. Lásd az alábbi táblázatot az angol ábécé és a számjegyek megfeleltetésére.
 

1 (i j)	2 (a b c)	3 (d e f)
4 (g h)	5 (k l)	6 (m n)
7 (p r s)	8 (t u v)	9  (w x y)
	0 (o q z)

Például, ha a telefonszám 941837296, akkor a neki megfelelő szó lehet a WHITEPAWN, és ha a telefonszám a 2855304, akkor pedig megfelelhet a BULLDOG szónak.
Adott használható szavaknak egy sorozata. Az a feladat, hogy egy adott telefonszámhoz add meg azt a legkevesebb szóból álló sorzatot, amelynek betűi rendre megfelelnek a telefonszám számjegyeinek.

Bemenet:

A PHONE.IN állomány első sora a telefonszámot tartalmazza, amely legfeljebb 100 jegyből áll. A második sor a használható szavak M számát tartalmazza (legfeljebb 50 000). Az állomány további M sora egy-egy használható szót tartalmaz. A szavak legfeljebb 50 kisbetűből állhatnak. Az állomány mérete legfeljebb 300 Kbyte.

Kimenet:

A PHONE.OUT állomány egyetlen sort tartalmaz, melyben egy olyan legkevesebb szóból álló sorozat van, ami megfelel a telefonszámnak. A szavak között pontosan egy szóköz legyen! Ha nincs megoldás, akkor a sor pontosan a ’No solution.’ szöveget tartalmazza. Ha több megoldás is van, akkor bármelyiket ki lehet írni az állományba, de csak egyet.

Példa:

 

PHONE.IN	PHONE.OUT
7325189087 5 it your reality real our	reality our
4294967296 5 it your reality real our	No solution.

Két barát a következő játékot játssza. Adottt egy nullákból és egyesekből álló számsorozat, amelyet a második játékos ismer. Az egyik játékos választ egy összefüggő részsorozatot, megadva annak kezdő és végző pozícióját. Megkérdezi, hogy a választott részsorozatban páros vagy páratlan számú egyes számjegy van-e. A második játékos nem biztos, hogy helyesen válaszol.
Az a feladat, hogy kiderítsük, melyik az az első kérdés, amelyre adott válasz ellentmondásban van a korábbi válaszokkal.

Bemenet:

A PARITY.IN állomány első sorában egyetlen szám van, a 0-1 sorozat hossza (ami legfeljebb 1 000 000 000). A második sorban egy pozitív egész szám van, a kérdések száma (ami legfeljebb 5 000). A további sorok tartalmazzák a kérdéseket és a rájuk adott válaszokat. Minden sor egy kérdést és egy választ tartalmaz. Két egész szám (i,j, ahol 1<=i<=j<=sorozat hossza) írja le a kérdést (az első a kérdezett részsorozat első elemének sorszáma, a második pedig az utolsóé) és a választ, ami az even, ha páros, illetve az odd, ha páratlan számú egyes van a második játékos szerint a kérdezett részsorozatban. A számok között, illetve a második szám és a válasz szava között egy-egy szóköz van.

Kimenet:

A PARITY.OUT állomány egyetlen X számot tartalmaz. X az a legkisebb szám, ameddig az első X válaszban nincs ellentmondás, de az X+1. válasszal már ellentmondáshoz jutunk. Ha nincs ellentmondás a válaszokban, akkor X a kérdések száma legyen, ami megegyezik a PARITY.IN második sorában levő számmal!

Példa:
 

PARITY.IN	PARITY.OUT
10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd	3
10 5 1 2 even 1 4 even 2 4 odd 1 10 even 3 10 even	5