Nemzetközi Informatikai Olimpia 1995

(26 kisbetű és a hozzájuk tartozó értékek)

A Játék a betűkkel egy népszerű otthoni és televíziós játék. A játék egyik változatában betűket kell gyűjteni. Minden betűhöz egy-egy érték tartozik.

Feladat:

A feladat: egy vagy több szó összeállítása a betűkből úgy, hogy a szavak a lehető legnagyobb pontszámot érjék el. Az ember ilyenkor minden lehetséges szóval megpróbálkozik, néha még a szótárat is segítségül hívja, majd nekilát kiszámítani a pontokat. Természetesen számítógéppel mindezt hatékonyabban meg lehet oldani.

Adott a betűk értéke (lásd a fenti ábrát), egy lista az angol szavakról, és a rendelkezésre álló betűkről. Találja meg a legnagyobb pontértékű szavakat, szópárokat, amiket a betűkből ki lehet rakni.

Bemenet:

Az INPUT.TXT állomány egy sort tartalmaz; a rendelkezésre álló betűket (kisbetűk `a'-tól `z'-ig). A sor minimum 3, maximum 7 betűt tartalmazhat, tetszőleges sorrendben.

A `szótár' állomány (WORDS.TXT) maximum 40,000 sort tartalmazhat. Az állomány végén egy pontot (`.') tartalmazó sor áll. Minden egyes sor egy-egy karakterláncot tartalmaz, ami minimum 3, maximum 7 kisbetűből áll. A WORDS.TXT ABC sorrendben tartalmazza a sorokat, és egyetlen sor sem szerepel benne kétszer.

Kimenet:

A kimenő állomány (OUTPUT.TXT) első sorában a legnagyobb elérhető pontszámnak kell állnia, majd minden ezt követő sor egy-egy ezzel megegyező pontértékű szót/szópárt tartalmaz a WORDS.TXT állományból. Egyik betű sem szerepelhet többször a kimenő állomány egy-egy sorában, mint a bemenő állományban. A pontérték kiszámításához használja az fenti ábrán látható értékeket.

Ha a megadott betűkből két szó is előállítható, akkor a két szónak - egy szóközzel elválasztva - ugyanabban a sorban kell szerepelnie. Ügyeljen arra, hogy a párok ne forduljanak elő kétszer. Például; a `rag prom' és a `prom rag' egy párnak számít, tehát csak egyszer kell szerepelnie a kimenő állományban. Egy sor ugyanazt a szót akár kétszer is tartalmazhatja, feltéve hogy ehhez elegendő betű áll rendelkezésre.

Példa:
 

WORDS.TXT	INPUT.TXT	OUTPUT.TXT
profile program prom rag ram rom .	prmgroa	24 program prom rag

10 állomásból álló verseny pályája

A fenti ábra egy utcai verseny pályájára mutat példát. A pályán állomások (0-tól N-ig sorszámozva, jelen esetben N=9), és az állomásokat összekötő nyilak találhatóak. A 0-ás állomás a verseny kiindulópontja, míg az N-es a cél. A nyilak egyirányú utcákat jelképeznek. A verseny  résztvevői állomásról állomásra haladnak az utcákon, mindig csak a nyíllal jelölt irányban. A résztvevő bármely állomásról bármely tovább menő utcát választhatja.

Feladat:

Egy jól kialakított pálya a következő feltételeknek felel meg:

• A startból kiindulva a pálya bármely állomása elérhető.
• A cél a pálya bármely állomásából elérhető.
• A célból nincsenek kimenő nyilak.

A résztvevőknek a célbaérkezéshez nem szükséges a pálya valamennyi állomását érinteniük. Azonban vannak elkerülhetetlen állomások. A fenti példában ilyen elkerülhetetlen állomás a 0-ás, 3-as, 6-os és 9-es állomás. Az irandó programnak egy, a feltételeknek megfelelő pályáról kell eldöntenie, hogy a pályán a startot és a célt kivéve melyek az elkerülhetetlen állomások (A részfeladat).

Tegyük fel, hogy a verseny két egymást követő napon kerül megrendezésre. Ekkor a versenypályát két pályára kell szétbontani, így minden napra jut egy-egy pálya. Az első nap a start a 0-ás állomásban van, a cél az `elválasztó állomásban'. A második nap a start az elválasztó állomásban van, míg a cél az eredeti cél állomásban (N). A programnak egy, a feltételeknek megfelelő pályáról kell eldöntenie, hogy melyek a pálya elválasztó állomásai (B részfeladat). A feltételeknek megfelelően kialakított C pályán az S elválasztó állomás a következő feltételeknek felel meg: S nem lehet a C pálya startja/célja, és a szétválasztott két pályának nem lehet S-en kívül közös pontja, valamint közös nem lehet közös nyila sem. A fenti példában egyedül a 3-as állomás felel meg ezeknek a feltételeknek, tehát ennek a pályának ez az egyetlen elválasztó állomása.

Bemenet:

Az INPUT.TXT állomány egy, a feltételeknek megfelelően megépített pályát ír le, ami maximum 50 pontot és 100 nyilat tartalmazhat. Az
állomány N+1 sorból áll. Az első N sor mindegyike a megfelelő állomásból (0-tól N-1-ig) kiinduló nyilak végpontjainak koordinátáját
tartalmazza. Minden sort a -2 zár le. Az állomány utolsó sora -1-et tartalmaz.

Kimenet:

A programnak két sort kell írnia a kimenő állományba (OUTPUT.TXT). Az első sornak az elkerülhetetlen állomások számát, valamint tetszőleges sorrendben eme állomások sorszámait kell, hogy tartalmazza (A részfeladat). A második sor az elválasztó állomások számát, és eme állomások sorszámait tartalmazza (B részfeladat).

Példa:

 

INPUT.TXT	OUTPUT.TXT
1 2 -2 3 -2 3 -2 5 4 -2 6 4 -2 6 -2 7 8 -2 9 -2 5 9 -2 -1	2 3 6 1 3

kábel 3 dróttal és 3 kapcsolóval

A fenti ábrán egy kábel látható, melyen az A oldalt három drót köti össze a B oldallal. Az A oldalon a három drót neve: 1, 2 és 3. A B oldalon az
1-es és a 3-as drót a 3-as kapcsolóhoz van kötve, míg a 2-es drót az 1-es kapcsolóhoz.

Általában a kábelek m drótot tartalmaznak (1<=m<=90), 1-től m-ig sorszámozva az A oldalon, és m kapcsolót 1-től m-ig sorszámozva a B
oldalon. Minden drót pontosan egy kapcsolóhoz csatlakozhat. A kapcsolókhoz nem kell drótnak csatlakoznia, de egy-egy kapcsolóhoz akár
több drót is csatlakozhat.

Feladat:

Az irandó programnak néhány mérés végrehajtásával kell eldöntenie, hogy miként csatlakoznak a drótok a kapcsolókhoz. Minden kapcsoló zárt, vagy nyitott állapotban lehet. Alapállapotban minden kapcsoló nyitva van. Egy drót az A oldalon egy P próbával tesztelhető: az L lámpa akkor, és csak akkor világít, ha az érintett drót egy zárt kapcsolóhoz csatlakozik.

Az írandó program először m értékét kéri be a billentyűzetről. A program három féle paranccsal válaszolhat az \emph-en {standard output}.
Minden parancs egy nagybetűvel kezdődik: T (egy drót tesztelése), C (kapcsoló állapotának módosítása), és D (kész). A T parancsot egy drót sorszáma, a C parancsot egy kapcsoló sorszáma, míg a D parancsot egy számokból álló lista követi; a lista i-ik eleme az i-ik drótot jelképezi, és azt mutatja meg, hogy ez az i-ik drót mely kapcsolóhoz van csatlakoztatva.

A T és C parancsot követően a programnak egy sort kell beolvasnia az \emph-ről{standard input}. A T parancsra I (Igen) a válasz, ha a drót kapcsolója zárva van (a lámpa világít). Ellenkező esetben a válasz N (Nem). A C utasításra I a válasz, ha a kapcsoló új állapota zárt, egyébként N. A C utasítás feladata, hogy a kapcsoló állapotát megváltoztassa (ha zárt volt, akkor nyitottá teszi, és ugyanez fordítva); a visszaadott eredmény csak egy visszajelzés.

Az ön programja tetszőleges sorrendben adhatja ki a T és C parancsokat. A programnak a futás befejezésekor egy D utasítást kell adnia a megfelelő listával. A program nem adhat ki több, mint kilencszáz (900) utasítást.

Példa:

 

Bemenet	Kimenet
C 3 T 1 T 2 T 3 C 3 C 2 T 2 D 3 1 3	3 I I N I N I N