Nemzetközi Informatikai Olimpia 2001

A kétszemélyes játékot egy olyan irányított gráfon játsszák, amelyek 1-től N-ig számozott csomópontjait elosztják a játékosok között. A csomópont értéke a csomópontba írt 1 és N közötti szám; minden csomópontnak a többitől különböző értéke van. Kezdetben mindkét játékosnak 0 pontja van. A játék az 1. számú csomóponttól indul, szabályai a következők:

1. Ha az aktuális csomópontba írt szám nagyobb, mint a csomópont tulajdonosának aktuális pontszáma, akkor ez lesz a tulajdonos új pontszáma, egyébként a pontszáma nem változik. A másik játékos pontszáma mindenképpen változatlan marad.
2. 2. Ezt követően az aktuális csomópont tulajdonosa kiválaszt egy olyan csomópontot, amelybe él vezet az aktuális csomópontból; a következő lépésben ez lesz az aktuális csomópont. Ha ez is az övé, akkor újra ő következik.

A játék akkor ér véget, ha valamelyik játékos visszajut a kezdő (első) csomópontba. Az győz, akinek a játék végén több pontja van.

Az irányított gráf olyan elrendezésű, hogy

• minden csomópontból vezet ki él,
• a kezdő csomópontból bármelyik csomópont elérhető valahány lépésben,
• a játék biztosan befejeződik véges számú lépés után.

Írj olyan programot, amely a fenti szabályok szerint játszik és győz. A programot csak olyan adatokkal tesztelik, hogy győzni tudjon, függetlenül attól, hogy ki lép először. Az ellenfél optimálisan játszik, azaz ha lehetőséget kap rá, akkor győz.

Bemenet és kimenet:

Programod a standard inputról olvas és a standard outputra ír. A te programod az 1-es, az ellenfél a 2-es játékos. Induláskor a programodnak a következőket kell beolvasnia.

Az első sorban a csomópontok N száma van (1 <= N <= 1000).
A következő N sor mindegyikében N egész szám van. Az I-edik sorban a J-edik szám 1, ha vezet él I-ből J-be, egyébként 0.
A következő sorban N egész szám van, ahol az I-edik szám az I-edik csomópont tulajdonosának a száma (1 vagy 2).
A következő sorban is N egész szám van; itt az I-edik szám az I-edik csomópontba írt érték.

Ezután következnek a játék lépései (az 1-es csomóponttól kezdve) az alábbiak szerint:

• Ha az aktuális csomópont tulajdonosa a te programod, akkor a következőnek kiválasztott csomópont számát ki kell írnia a standard outputra.
• Ha az aktuális csomópont tulajdonosa az ellenfél programja, akkor a progra-modnak a következő csomópont számát be kell olvasnia a standard inputról.

Példa:

Az ábrán körrel jelölt csomópontok tulajdonosa az 1-es, a négyzettel jelölteké a 2-es játékos. A csomópont mellé írt szám a csomópontot azonosító szám, a csomópontba írt szám pedig a csomópont értéke.

BEMENET	KIMENET	Magyarázat
4		N
0 1 0 0		Az 1. csomópontból kivezető élek leírása
0 0 1 1		A 2. csomópontból kivezető élek leírása
0 0 0 1		A 3. csomópontból kivezető élek leírása
1 0 0 0		A 4. csomópontból kivezető élek leírása
1 1 2 2		A csomópontok tulajdonosai
1 3 4 2		A csomópontok értékei
	2	Az 1-es játékos lépése.
	4	Az 1-es játékos lépése.
1		A 2-es játékos lépése a kezdő helyre.

A játék végén az 1-es játékosnak 3, a 2-esnek 2 pontja van, így az 1-es győzött.

Programozási tamácsok:

Az alábbi példákban a target egész változó az aktuális csomópont sorszáma.

Ha C++ nyelven az iostreams modult használod, a következőképpen olvass, illetve írj:

cin>>target;
cout<<target<<endl<<flush;

Ha C vagy C++ nyelven a scanf és printf eljárásokat használod, a következő-képpen olvass, illetve írj:

scanf ("%d", &target);
printf("%d\n",target); fflush (stdout);

Pascal nyelven a következőképpen olvass, illetve írj:

Readln(target);
Writeln(target);

Segédeszközök:

Kapsz egy programot (Linux: score2, Windows: score2.exe), amely a score.in állományból beolvasott, a kiinduló helyzetet leíró adatokat kiírja a standard outputra, olyan formában, ahogyan azt a programod várja a standard inputról. Ezt felhasználhatod a programod tesztelésére. Ezután (véletlenszerű stratégiát alkalmazva) a standard inputról beolvassa a programod által kiírtakat, és kiírja a saját lépéseit a standard outputra.

Pontozás és értékelés:

Ha a programod nyer, megkapod a maximális pontszámot, egyébként 0 pontot kapsz tesztesetenként.

Az értékelés során a programod először egy másik programmal játszik olyan időkorlát mellett, amely 1 másodperccel nagyobb a megadott időkorlátnál. A programod input és output adatait tárolják. Ezután a programodat újra futtatják az előzőleg eltárolt és most egy állományból beolvasott input adatokkal és a megadott időkorláttal, és veszik figyelembe értékeléskor. A programodnak ugyanazt az eredményt kell adnia, mint az előző futtatásakor.

Az AES (Advanced Encryption Standard) kódoló algoritmus három 128 bites blokkal dolgozik. p a kódolandó üzenet, k a kulcs és c az E függvénnyel előállított kódolt üzenet blokkja:

c = E(p, k)

Az E kódoló függvény inverze az a D dekódoló függvény, amelyre

D ( E(p, k), k ) = p ,     E ( D(c, k), k ) = c

A kettős AES algoritmus két független kulcsot használ: először k1-et, azután k2-t:

c2 = E ( E(p, k1), k2 )

A kulcsoknak csak az első 4*s bitje (az első s hexadecimális jegye) számít, a többi bitjük 0 értékű.
Kettős AES algoritmussal kódolt üzenetek kulcsait kell megfejtened a kódolandó és a kódolt üzenet, valamint az s ismeretében.
A kódoló és a dekódoló függvények megtalálhatók a könyvtárban.
Nem a programot, hanem a megfejtett kulcsokat kell beadni.

Bemenet:

10 különböző kulcspárt kell megfejtened a double1.in … double10.in állományok adataiból (mindre van megoldás). Minden állományban három sor van. Az elsőben van az s egész szám, a másodikban a kódolandó p üzenet, a harmadikban pedig a kettősen kódolt c2 üzenet. Mindkét üzenet 32 hexadecimális számjegyből ('0'..'9', 'A'..'F') áll. (A könyvtár egyik eljárása konvertálja a stringet blokká.)

Kimenet:

10 output állományt kell előállítanod. Minden állományban három sor legyen. Az első sorba az I-edik input állomány esetén a következő szöveget írd:

#FILE double I

A második sorba a k1, a harmadik sorba a k2 kulcsot kell írnod. Mindkét kulcs 32 hexadecimális számjegyből ('0'..'9', 'A'..'F') álljon! (A könyvtár egyik eljárása konvertálja a blokkot karakteres formára.) Ha több megoldás van, akkor is csak egyet kell kiírnod.

Példa:

 

DOUBLE.IN	DOUBLE.OUT
1 00112233445566778899AABBCCDDEEFF 6323B4A5BC16C479ED6D94F5B58FF0C2	#FILE double 0 A0000000000000000000000000000000 70000000000000000000000000000000

Könyvtár:

FreePascal könyvtár

Linux: aeslibp.p, aeslibp.ppu, aeslibp.o;
Windows: aeslibp.p, aeslibp.ppw, aeslibp.ow
type
  HexStr = String [ 32 ]; { only '0'..'9', 'A'..'F' }
  Block  = array [ 0..15 ] of Byte; { 128 bits }

procedure HexStrToBlock ( const hs: HexStr; var b: Block );
procedure BlockToHexStr ( const b: Block; var hs: HexStr );
procedure Encrypt ( const p, k: Block; var c: Block );
  { c = E(p,k) }
procedure Decrypt ( const c, k: Block; var p: Block );
  { p = D(c,k) }

Az aestoolp.pas program bemutatja a FreePascal könyvtár használatát.

GNU C/C++ könyvtár (Linux és Windows: aeslibc.h, aeslibc.o):
 

typedef char HexStr[33]; /* '0'..'9', 'A'..'F', '\0'-terminated */
typedef unsigned char Block[16];  /* 128 bits */

void hexstr2block ( const HexStr hs, /* out-param */ Block b );
void block2hexstr ( const Block b, /* out-param */ HexStr hs );
void encrypt ( const Block p, const Block k, /* out-param */ Block c );
  /* c = E(p,k) */
void decrypt ( const Block c, const Block k, /* out-param */ Block p );
  /* p = D(c,k) */

Az aestoolc program bemutatja a GNU C/C++ könyvtár használatát.

Korlátok:

1 <= s <= 5

Megjegyzés:

10 mp-en belül minden input állomány esetén meg lehet fejteni a kulcsot.

Egy téglalap alapú raktár négyzetes cellákra van osztva. A cellákat felülről lefelé, ill. balról jobbra haladva 1-től kezdve számozzuk.

A raktárban egyedi számmal jelölt konténerek vannak, cellánként legfeljebb egy. A konténerek száma (N) kisebb mind az oszlopok, mind a sorok számánál.

Egy munkás egy k jelű konténert a bal felső saroktól kezdve az alábbi algoritmus szerint helyez el:

Az első sorban balról jobbra haladva keres egy k-nál nagyobb jelű konténert. Ha ilyen nincs, akkor a k jelű konténert a sorban a legutolsó konténer utáni cellára teszi. Ha talál ilyet, akkor kicseréli a k jelű konténerrel, és a kivett konténert ugyanezzel a módszerrel helyezi el a következő sorban. Ha ez a sor még üres, akkor a konténert a sorban az első cellára rakja. A folyamat akkor ér véget, ha a konténert nem egy másik konténer helyére tette.

Ha a konténerek a 3, 4, 9, 2, 5, 1 sorrendben érkeznek, akkor a végén a raktárban így helyezkednek el:
 

1 4 5
2 9
3


Ugyanez az elrendezés más érkezési sorrend mellett is előállhat, pl. 3,2,1,4,9,5, vagy 3,2,1,9,4,5 vagy még 14 más érkezési sorrend esetén. Írj olyan programot, amely adott elrendezésre előállítja az összes lehetséges érkezési sorrendet.

Bemenet:

A depot.in állomány első sorában a raktár konténert tartalmazó sorainak R száma van. A raktár első R sorát írja le az állomány következő R sora: mindegyik elején az adott raktári sorban elhelyezett konténerek M száma van, ezt követi az adott sorban elhelyezett konténerek jele (M db egész).

Korlátok:

1 <= N (a raktárban elhelyezett konténerek száma) <= 13, 1 <= k (egy konténer jele) <= 50.

Kimenet:

A depot.out állományba annyi sort kell írni, ahány lehetséges érkezési sorrend van. Minden sorba N számot kell írni, az N konténer jelét egy lehetséges érkezési sorrendben. A érkezési sorrendeknek különbözőknek kell lenniük, tetszőleges sorrendben lehetnek.

Példa:
 

DEPOT.IN	DEPOT.OUT
3 3 1 4 5 2 2 9 1 3	3 2 1 4 9 5  3 2 1 9 4 5  3 4 2 1 9 5  3 2 4 1 9 5  3 2 9 1 4 5  3 9 2 1 4 5  3 4 2 9 1 5  3 4 9 2 1 5  3 2 4 9 1 5  3 2 9 4 1 5  3 9 2 4 1 5  3 4 2 9 5 1  3 4 9 2 5 1  3 2 4 9 5 1  3 2 9 4 5 1  3 9 2 4 5 1
2 2 1 2 1 3	3 1 2 1 3 2

Pontozás:

Tesztesetenként:
0 pont jár, ha valamelyik sorban lehetetlen vagy hibás érkezési sorrend van.
4 pont jár, ha minden lehetséges érkezési sorrend pontosan egyszer fordul elő.
2 pont jár, ha az összes lehetséges érkezési sorrendnek legalább a fele pontosan egyszer fordul elő.
1 pont jár, ha az összes lehetséges érkezési sorrendnek kevesebb, mint a fele fordul elő, vagy van olyan, amelyik többször fordul elő.