Nemzetközi Informatikai Olimpia 1997

“iShongololo” a százlábú Zulu neve. Az iShongololo hosszú, fényes, fekete, soklábú rovar.

Az iShongololo gyümölcsöt eszik. A feladat kedvéért feltesszük, hogy a “gyümölcs” hasáb alakú, hossza L, szélessége W, magassága pedig H.

Feladat:

Írj olyan programot, amely maximalizálja az iShongololo által megevett blokkok számát az alábbi korlátozások betartása mellett. A program eredményül állítsa elö az iShongololo tevékenységsorozatát, miközben átrágja magát a gyümölcsön.

Az iShongololo a gyümölcsön kívülről indul. Az első blokk, amelyet az iShongololonak meg kell ennie, az 1,1,1 jelű, és utána be kell lépnie ebbe a blokkba. Megáll, ha nem tud több blokkot szabályszerűen megenni, és ha nem tud továbblépni.

Korlátozások:

1. Az iShongololo pontosan egy üres blokkot foglal el.
2. Az iShongololo egy-egy alkalommal pontosan egy egész blokkot eszik meg.
3. Az iShongololo nem léphet olyan helyre, ahol már volt (azaz nem léphet visszafelé, és nem keresztezheti saját járatát).
4. Az iShongololo nem léphet olyan blokkba, amit még nem evett meg, és nem léphet ki a gyümölcsböl.
5. Az iShongololo csak olyan blokkot ehet meg vagy olyan blokkba léphet be, amelynek van közös oldala az általa elfoglalt blokkal. Csak olyan blokkot ehet meg, amelynek egyetlen oldala sem közös olyan üres blokkal, amelyet már korábban felzabált.

Bemenet:

A program olvasson be három egész számot: a hasáb hosszat (L), szélességét (W) és magasságát (H).

A három szám (L,W,H) három külön sorban van. Mindhárom szám értéke legalább 1 és legfeljebb 32.

Kimenet:

A kimenet “E” (eszik) vagy “M” (mozog) betüvel kezdődő sorokból áll. A betűt három egész szám követi az L,W,H sorrendjében, amelyek az adott lépésben felzabált blokkot írják le, vagy azt a blokkot, ahova az iShongololo lépett.

Példa:
 

TOXIC.DAT	TOXIC.OUT
2 3 2	E 1 1 1 M 1 1 1 E 2 1 1 E 1 1 2 E 1 2 1 M 1 2 1 E 1 3 1 M 1 3 1 E 2 3 1 E 1 3 2 M 1 3 2

Pontozás:

• Ha az iShongololo megsérti a korlátozásokat, a megoldásra 0 pontot adunk.
• A teljes pontszám a megevett blokkok számának százalékos aránya az általunk ismert legjobb megoldáshoz képest.
• A kapott pontszám nem lehet több 100%-nal.

Egy jövőbeli Mars-utazás során egy olyan szállítóeszköz  fog leszállni a Mars felszínére, amely több Mars-kutató jármüvet (MKJ) szállít. Az MKJ-k a szállítóeszköz  leszállási helyéről indulnak útnak az adóállomás felé, amely a szállítóeszköztől nem messze száll le. Az MKJ-knek az adóállomás felé haladtukban kőzetmintákat kell gyűjteniük. Egy kőből csak egyszer lehet mintát venni; az az MKJ vesz mintát, amelyik először jut el a kőhöz. Ezután ugyanabból a kőből nem lehet többször mintát venni, de más MKJ áthaladhat ugyanazon a helyen.

Az MKJ-k nem tudnak sziklás terepen mozogni.

A járműveket úgy tervezték, hogy a szállítóeszköztől az adóállomásig tartó rácsos úthálózaton csak dél vagy kelet felé mozoghatnak. Ugyanabban az időben egynél több MKJ is lehet ugyanazon a helyen.

Figyelmeztetés: Ha egy MKJ nem tud szabályszerűen eljutni az adóállomáshoz, az általa gyűjtött kőzetminták végérvényesen elvesznek.

Feladat:

Határozd meg az egyes MKJ-k mozgását úgy, hogy a pontszámod maximális legyen, azaz a lehető legtöbb MKJ-vel a lehető legtöbb kőzetmintát juttasd el adóállomásra!

Bemenet:

Az égitest felszínét a szállítóeszköz és az adóállomás közötti területen egy P*Q méretü rács írja le. A szállítóeszköz mindig az (1,1), az adóállomás pedig mindig a (P,Q) helyen van. A különböző területfajták jelölése a következö:
 

Üres terület	0
Sziklás terület	1
Közetmintás terület	2

 A bemeneti állomány tartalma:
 

MKJkSzáma P Q (X1Y1)   (X2Y1)   (X3Y1)...  (XP-1Y1)   (XPY1) (X1Y2)   (X2Y2)   (X3Y2)...  (XP-1Y2)   (XPY2) (X1Y3)   (X2Y3)   (X3Y3)...  (XP-1Y3)   (XPY3) ... (X1YQ-1) (X2YQ-1) (X3YQ-1)...(XP-1YQ-1) (XP-1YQ-1) (X1YQ)   (X2YQ)   (X3YQ)...  (XP-1YQ)   (XPYQ)

P és Q a rács mérete. MKJ-k száma 1000-nél kisebb egész szám, amely a szállítójárműből útnak indított MKJ-k számát adja meg. E három adatot Q db sor követi, minden sor a terület egy-egy sorát ábrázolja, a soron belül a számokat egy-egy szóköz választja el. P és Q nem nagyobb 128-nál.

Kimenet:

Egymás utáni sorok, amelyek az MKJ-k mozgását írják le a szállítóeszköztől az adóállomásig. Minden sorban egy MKJ sorszáma, továbbá (szóközzel elválasztva) a 0 vagy az 1 számjegy van, ahol a 0 a déli, 1 pedig a keleti irányban megtett lépést jelenti.

Példa:

 

MARS.DAT	MARS.OUT
2 10 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 1 0 1 2 0 0 0 0 1 0 1 0 0 2 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0	1 1 1 0 2 1 2 0 1 1 1 1  2 0  2 1  2 0  2 0  2 0  2 0  1 1  1 0  1 0  1 0  1 0  1 0  1 0  2 0  2 1  1 1  1 1  1 1  1 1  1 1  2 1  2 1  2 1  2 1  2 1  2 1

Pontozás:

A pontozás az összegyűjtött és az adóállomásra eljuttatott kőzetminták számán alapul, de ezt az adóállomást elérő, illetve el nem érő MKJ-k száma módosítja.

• Egy szabálytalan lépés érvényteleníti az addig helyes megoldást, és a végső pontszám 0 lesz. A lépés szabálytalan, ha az MKJ sziklás területre lép vagy ha elhagyja a rácsot.
• Pontszám = (az összegyűjtött és az adóállomáshoz eljuttatott kőzetminták száma + az adóállomáshoz eljutott MKJ-k száma – az adóállomáshoz el nem jutott MKJ-k száma) az adott bemeneti állományra, maximálisan megszerezhető pontok százalékában.
• Az adott bemeneti állományra kapott pontszám maximum 100% és minimum 0% lehet.

A játék célja, hogy a játékosok hatszög alakú cellákból álló táblán zsetonok lerakásával saját utat építsenek a tábla szemben levö két széle között.

A Hex játék szabályai

A Hex kétszemélyes játék, amelyet NxN darab hatszög alakú cellából álló, rombuszalakú táblán játszanak. Az alábbi ábra az N=6 esetet mutatja. (row=sor, column=oszlop)

1. A két játékos egyike a Te programod, a másikat egy modul valósítja meg.
2. Mindig a Te programod lép elöször.
3. A játékosok felváltva tesznek a táblára egy zsetont.
4. Zseton a tábla bármely üres cellájára tehetö.
5. Két cellát szomszédosnak mondunk, ha van közös oldaluk.
6. Egy adott játékos két szomszédos cellán lévö zsetonja egyszerü utat alkot a két cella között.
7. Két cella között akkor van út, ha egyik cellából a másikba egymáshoz kapcsolódó egyszerü utakon el lehet jutni.

Feladat:

• Írj programot, amely a Hex játékot játsza.
• Az elsö játékos (a programod) célja, hogy utat építsen az elsö oszlop valamely, tetszőleges cellája és az N. oszlop tetszőleges cellája között.
• A másik játékos (a modul) arra törekszik, hogy az elsö sor és N. sor között létesítsen hasonlóképpen utat.
• A programod mindig győzhet, ha jól játszik.

Be- és kimenet:

A programodnak nem kell sem file-ból olvasni, sem abba írni. A programodnak nincs szüksége billentyűzet-inputra és nem írhat a képernyőre sem. Minden bemenő adatot a modul függvényei szolgáltatnak. A modul gondoskodik a szükséges output HEX.OUT nevű fileba írásáról. Ennek a tartalmával nem kell törődnöd.

Induláskor a tábla nem feltétlenül üres, hanem egy olyan szabályos játékállást tartalmaz, amelyből az első játékos még nyerhet. Programod a GetMax és a LookAtBoard függvényekkel kérdezheti le a kezdeti játékállást. A játék kezdetekor mindkét játékosnak azonos számú zsetonja van a táblán.

Feltételek:

1. A tábla méretére (N-re) teljesül: 1<=N<=20.
2. Programod legfeljebb 200 zsetont tehet le a játék során. A játék összideje (a teljes program futásideje) legfeljebb 40 másodperc lehet, ebből a másik játékos (a modul) legfeljebb 20 másodpercet fogyaszt.

A modul:

Rendelkezésedre áll a HexLib modul, amely a másik játékos játékát valósítja meg. Ezt a modult programodnak „importálnia” kell.
A feladat könyvtárában találsz olyan példákat, amelyek ennek módját mutatják az egyes nyelvekben:
TESTHEX.CPP, TESTHEX.C, TESTHEX.PAS és  TESTHEX.BAS.
A HexLib  modul függvényei és eljárásai a következök:
(Pascal, C/C++ és Basic sorrendben)
 

function LookAtBoard (row, column: integer): integer; int LookAtBoard (int row, int column); declare function LookAtBoard cdecl (byval x as integer, byval y as integer)

Eredménye:  –1  ha row<1 vagy row>N vagy column<1 vagy column>N   0  ha nincs zseton az adott pozíción   1  ha az adott pozíción levö zseton az 1. játékosé   2 ha az adott pozíción levö zseton a 2. játékosé (a modulé).

 

procedure PutHex (row, column: integer); void PutHex (int row, int column); declare sub PutHex cdecl (byval x as integer, byval y as integer)

Elhelyezi az 1. játékos egy zsetonját  a megadott row,column pozíciójú cellára, ha az üres.

 

function GameIsOver: integer; int GameIsOver (void); declare function GameIsOver cdecl ()

A következö egész értékek egyikét adja vissza: 0  ha a játéknak nincs még vége 1  ha minden cellán van zseton 2  ha az 1. játékos gyözött 3 ha a 2. játékos gyözött.

 

procedure MakeLibMove; void MakeLibMove(void); declare sub MakeLibMove cdecl ()

A 2. játékos lépését hajtja végre. Ennek eredménye a LookAtBoard és egyéb függvények segítségével kérdezhetö meg.

 

function GetRow: integer; int GetRow (void); declare function GetRow cdecl ()

Visszaadja a 2. játékos utoljára elhelyezett zsetonjának sorindexét, vagy -1-t, ha még nem volt ilyen.

 

function GetColumn: integer; int GetColumn (void); declare function GetColumn cdecl ()

Visszaadja a 2. játékos utoljára elhelyezett zsetonjának oszlopindexét, vagy -1-t, ha még nem volt ilyen.

 

function GetMax: integer; int GetMax (void); declare function GetMax cdecl ()

A tábla méretét (N) adja vissza.

Pontozás:

• Ha a programod nyer, a teljes pontszámot megkapod az adott tesztesetre.
• Ha a programod veszít, akkor a tesztesetre járó pontszám 20%-át kapod.
• 0 pontot kapsz az adott tesztesetre, ha programod a játék vége elött megáll, vagy kifut az idöböl.