Nemzetközi Informatikai Olimpia 1999

A virágüzlet kirakatát a lehető legszebben akarod berendezni. Több különböző virágcsokor van, és legalább ugyanannyi váza. Minden csokrot bele kell rakni valamelyik vázába. Minden vázában legfeljebb egy csokor lehet. Ha több váza van, mint csokor, akkor néhány váza üresen marad. A csokrokat és a vázákat 1-től kezdődő sorszámuk azonosítja. Ha i<j, akkor az i-edik csokornak kisebb sorszámú vázában kell lennie, mint a j-edik csokornak.
A váza-csokor párok esztétikai értékét egy-egy egész számmal adjuk meg, amint azt a táblázatban szereplő példa mutatja. Az üres váza esztétikai értéke 0.
 

		Vázák
		1	2	3	4	5
Virágcsokrok	1 (azálea)	7	23	-5	-24	16
	2 (begónia)	5	21	-4	10	23
	3 (szekfű)	-21	5	-4	-20	20

A táblázat szerinti esetben például az azálea jól illik a 2. és rosszul a 4. vázához.
A lehető legszebb elrendezés mellett az esztétikai értékek összege maximális. Ha egynél több megoldás van, közülük bármelyik megadható.

• 1<=F<=100, ahol F a csokrok száma.
• F<=V<=100, ahol V a vázák száma.
• -50<=A_i,j<=50, ahol A_i,j az i-edik csokorból és j-edik vázából álló pár esztétikai értéke.

Bemenet:

A flower.inp állomány tartalma:

• az első sorban az F és a V szám van szóközzel elválasztva,
• a következő F db sor mindegyikében V db egész szám van, azaz az A_i,j esztétikai érték az állomány (i+1)-edik sorának j-edik száma.

Kimenet:

A flower.out állomány pontosan két sorból áll:

• az első sorban a lehető legszebb elrendezéshez tartozó esztétikai értékek összege legyen,
• a második sorban F db számból álló olyan sorozat legyen, amelynek k-adik eleme a k-adik csokrot tartalmazó váza sorszáma.

Példa:
 

FLOWER.INP	FLOWER.OUT
3 5 7 23 –5 –24 16 5 21 –4 10 23 –21 5 –4 –20 20	53 2 4 5

Adott egy szöveg és kódszók egy sorozata. A szövegben egy olyan üzenet van elrejtve, amely a megadott kódszókból áll.

A kódszókban és a szövegben kizárólag az angol ábécé kis- és nagybetűi fordulnak elő. A kis- és nagybetűket megkülönböztetjük egymástól. A szövegben előforduló kódszó betűi között más betűk is lehetnek. Például az AuLvL szöveg, ahol u és v tetszőleges (esetleg üres) karaktersorozat, tartalmazza az ALL kódszót. Általában azt mondjuk, hogy az A szövegrész illeszkedik a B kódszóra, ha A és B első, ill. utolsó betűje azonos, és A-ból nulla vagy több betű elhagyásával kapható meg a B.

Egy kódszóra több, esetleg egymást átfedő szövegrész is illeszkedhet. Több kódszóra is illeszkedhet ugyanaz a szövegrész. Az is előfordulhat, hogy egy kódszóra egyetlen szövegrész sem illeszkedik.

Az illeszkedő szövegrészt első és utolsó karakterének szövegbeli sorszáma azonosítja. A szöveg karaktereit 1-től sorszámozzuk. A c1 és c2 szövegrészek nem fedik át egymást, ha c1 első betűjének sorszáma nagyobb (>) c2 utolsó betűjének sorszámánál, vagy fordítva.

A megoldás szövegrészek olyan halmaza, amelyben mindegyik szövegrész illeszkedik valamelyik kódszóra, továbbá

• a szövegrészek nem fedik át egymást,
• a szövegrészek hossza nem több 1000-nél,
• azon kódszók hosszának összege, amelyekre a szövegrészek illeszkednek, maximális.

Ha több helyes megoldás is van, közülük csak egyet kell megadni.

Feltételek:

• 1<= N<=100, ahol N a kódszók száma.
• A kódszók hossza legfeljebb 100.
• 1 <= a szöveg hossza <= 1 000 000.

Azt mondjuk, hogy a C szövegrész a W kódszóra jobb-minimálisan illeszkedik, ha C egyetlen kezdőszelete sem illeszkedik W-re. Például az ALL kódszóra az AAALAL jobb-minimálisan illeszkedik; az AAALALAL ugyancsak illeszkedik, de nem jobb-minimálisan.

A vizsgálandó szövegben

• a vizsgálandó szöveg minden egyes pozíciójára az azt a pozíciót tartalmazó jobb-minimálisan illeszkedő és egymást átfedő szövegrészek száma legfeljebb 2500,
• a jobb-minimálisan illeszkedő szövegrészek száma legfeljebb 10 000.

Bemenet:

Két bemenő állomány van: words.inp és text.inp.

• A words.inp első sorában a kódszók N száma van. A következő N sor mindegyike egy-egy kódszót tartalmaz. A kódszókat állománybeli sorrendjük szerint sorszámozzuk 1-től N-ig.
• A text.inp állomány egyetlen sorában a vizsgálandó szöveg van. A szöveget sorvég-jel, majd filevég-jel zárja.

Kimenet:

• A codes.out állomány első sorába a megoldáshoz tartozó összeget kell írni.
• A következő sorokba a megoldáshalmaz egy-egy elemét kell írni. Minden elem három számból álljon: a kódszó sorszámából, amire az adott szövegrész illeszkedik, valamint a szövegrész első és utolsó karakterének szövegbeli sorszámából.

Példa:
 

 

words.inp	text.inp	codes.out
RuN RaBbit HoBbit StoP	StXRuYNvRUHoaBbvizXztNwRRuuNNP	12 2 9 21 1 4 7 1 24 28

Kappadókiában, a földalatti városban, a sötétben a kijáratot keresve, egy térképre bukkansz. Sajnálatos módon a térkép nem jelzi, hol vagy, ezt a város felderítésével neked kell kitalálnod.
A város térképe olyan négyzetháló, ahol a négyzetek vagy O betűvel jelölt üres mezőt, vagy W betűvel jelölt falat jelentenek. Van nálad iránytű, így a térképet be tudod tájolni. A mező, ahol állsz, üres.
A megoldást a start (paraméter nélküli) eljárás meghívásával kell kezdened. A város felderítésére a look és a move eljárást használhatod.
A look(dir) függvényeljárás-hívással arra a kérdésre kapsz választ, hogy a dir irányba eső, szomszédos mező üres-e. A dir paraméter négy lehetséges értéke 'N', 'S', 'E' és 'W', a függvényhívás eredménye pedig az 'O' betű, ha dir irányban a szomszédos mező üres, és a 'W' betű, ha ott fal van ('N' = észak, 'S' =dél, 'E' = kelet, 'W' = nyugat).
A move(dir) eljáráshívással léphetsz át dir irányban a szomszédos mezőre. Természetesen csak üres mezőre léphetsz. Bármely üres mezőről bármely másik üres mezőre el lehet jutni.

A feladat az, hogy a lehető legkevesebb számú look -függvényhívással kitaláld, melyik mezőn volt a térkép. Ha kitaláltad, a finish(x, y) eljáráshívással kell közölnöd az eredményt, ahol x a vízszintes (kelet-nyugati), y pedig a függőleges (észak-déli) koordinátát jelenti.

Feltételek:

• 3<=U<=100, ahol U a térkép szélessége, azaz a mezők száma kelet-nyugati irányban.
• 3<=V<=100, ahol V a térkép magassága, azaz a mezők száma észak-déli irányban.
• A várost fal veszi körül, amely a térképen is látszik.
• A város délnyugati sarkának koordinátája (1,1), az északkeleti sarok koordinátája pedig (U,V).

Bemenet:

Az under.inp állományban

• az első sorban az U és a V számok vannak,
• a következő V db sor a négyzetháló egy-egy (vízszintes) sorát tartalmazza. Minden sor U db karakterből áll, ahol (V-y+2)-edik sor x-edik karaktere a térkép (x,y) koordinátájú mezőjét jellemzi az 'O' vagy a 'W' betű megadásával. Az adatok szóközt nem tartalmazhatnak.

Kimenet:

Kimeneti állomány nem kell létrehozni. Az eredményt a finish(x,y) eljáráshívás révén kell közölnöd.

Példa:
 

UNDER.INP	lehetséges párbeszéd
5 8 WWWWW WWWOW WWWOW WOOOW WOWOW WOOWW WWOOW WWWWW	start; look(’N’) ’W’ look(’E’) ’O’ move(’E’) look(’E’) ’W’ finish(3,5)

Útmutató:

A forrásprogramba írd bele a következő sort:

Uses undertpu;

Ez a tpu a következő eljárásokat és függvényeljárásokat definiálja:

Procedure start; {ezt kell először meghívni}
Function look(dir: char):char;
Procedure move(dir: char);
Procedure finish(x,y: integer); {ezt kell utoljára meghívni}

Értékelés:

Időlimit: 5 másodperc.
Egy-egy tesztesetre a teljes pontszámot (jelöljük A-val) az olyan program kapja meg, amelyre a look-hívások x száma nem több, mint az értékelő program által beállított M szám. (M nagyobb, mint a lehetséges minimum.) M például nem függ attól, hogy az irányokat az óramutató járásával megegyező vagy ellenkező sorrendben vesszük-e figyelembe. Részpontszám jár az olyan megoldásra, amelyre M<x<2M.

A végleges pontszámot az alábbi képlettel határozzuk meg:

A,         ha x<=M
A(2M-x)/M, ha M<x<2M
0,         ha x>=2M

A programra hibás működés esetén 0 pontot adunk. Hibásan működik a program a következő esetekben:

• eljárás vagy függvényhívás érvénytelen paraméterrel,
• fal felé lépne move-hívással,
• nem tartja az előírt hívási sorrendet (start ... finish).

Értékelés:

Készíts egy szöveges állományt place.txt néven, amely a kitalálandó mező koordinátáit tartalmazza. Futtasd a programodat. Az eredményt a result.txt állományban találod.

A place.txt állományban egyetlen sorban két szám legyen, a kitalálandó mező vízszintes és függőleges koordinátája. Magadnak kell létrehoznod az under.txt bemeneti állományt is. A result.txt állományban két sort találsz. Az első sorban a finish(x,y) eljáráshívásban megadott (x,y) koordinátapár van, a másodikban pedig a "You used look nnn times" üzenet, ahol nnn a programod által végrehajtott look-hívások száma.

Fontos tudni, hogy ezzel csak azt tudod ellenőrizni, hogy a programod helyesen használja-e a megadott eljárásokat, azt nem, hogy a megoldásod jó-e.