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

Tekintsük az alábbi eszközzel játszható játékot:

Az eszköz különböző hosszúságú vízszintes lapokat tartalmaz, különböző magasságban elhelyezve. A legalsó lap a földön van (0 magasságban, végtelen hosszal).

A labda egy adott pontról indul lefelé a 0. időpontban, állandó sebességel, egy időegység alatt 1 métert tesz meg. Ha a labda egy lapra ér, akkor a lapon, annak valamelyik vége felé haladhat tovább, ugyanekkora sebességgel. Amikor eléri a szélét, akkor újra lefelé megy. Lefelé haladva nem tehet meg lap érintése nélkül MAX méternél nagyobb távolságot.

Feladat:

Írj programot, amely megadja a labda egy olyan útját, amin a lehető leghamarabb leér a földre!

Bemenet:

Állománynév: FALL.IN
1. sor: N X Y MAX (Négy egész szám, egy-egy szóközzel elválasztva: N a lapok száma (a földet nem számítjuk bele), X Y a labda kezdeti helyének vízszintes, illetve függőleges koordinátái, MAX pedig az a távolság, aminél többet nem lehet egyszerre lefelé megtenni. A lapokat 1-től N-ig sorszámozzuk.)
2..N+1. sorok: X1_i X2_i H_i (Három egész szám, egy-egy szóközzel elválasztva. Az i-edik lap H_i magasságban van, az X1_i és X2_i vízszintes koordináták között, a határokat is beleértve (X1_i<X2_i, i=1..N).)

Megjegyzés:

• A labda kiterjedés nélküli, a lap vastagság nélküli. Ha a labda pontosan a lap szélére esik, úgy tekintjük, hogy érinti azt a lapot, mehet tovább lefele is, és a lapon haladva is.
• A lapoknak nincs közös pontja.
• A tesztekre mindig van megoldás.
• Minden adat méterben van megadva.

Kimenet:

Állománynév: FALL.OUT
1. sor: TIME (Egy egész szám: az az időpont, amikor a labda leér a földre.)
A további sorok tartalma, az állomány végéig: P T D

• Három egész szám, egy-egy szóközzel elválasztva. A labda a P-edik lapot a T-edik időpontban éri el, és tőle D irányban megy tovább lefelé (0, ha balra és 1, ha jobbra).
• A föld elérését már nem szabad kiírni.
• A sorok T növekvő sorrendjében legyenek kiírva.

Megjegyzés:

Ha több megoldás is van, akkor csak egyet kel kiírni.

Korlátok:

1 < = N < = 1000
-20000 < = X1_i, X2_i < = 20000 (i=1..N)
0 < H_i < Y < = 20000

Példa:
 

FALL.IN	FALL.OUT
3 8 17 20 0 10 8 0 10 13 4 14 3	23 2 4 1 1 11 1 3 16 1

Tekintsük az alábbi kétszemélyes játékot:
Egy táblán N sorban vannak pálcikák, az i-edik sorban S_i darab van (1 < = i < = N). A pálcikákat az i-edik sorban 1-től S_i-ig sorszámozzuk. A játékosok felváltva lépnek. Minden egyes lépésben 1, 2 vagy 3 egymás mellett levő pálcikát lehet levenni valamelyik sorból, azaz a sorszámuknak folytonosnak kell lenni.
Például, ha egy sorban 10 pálcika van, és az első játékos leveszi a 4, 5, 6 sorszámú pálcikákat, akkor az 1, 2, 3, 7, 8, 9, és 10 sorszámú pálcikák maradnak. A második játékos elveheti például az 1, 2, 3 sorszámúakat (van más szabályos lépés is), de nem veheti el a 3, 7, 8 sorszámúakat, mert ezek nem folytonosak.
Az a játékos győz, aki az utolsó pálcikát veszi le a tábláról.

Feladat:

Írj programot, amely a nyerő stratégiával játszik a gép ellen.

---

Programodnak a gép ellen kell játszania. A géppel való párbeszédet az alábbi modul valósítja meg:

- Pascal: STICKS.TPU unit
- C/C++: sticks.h header, sticks.obj

Melyek az alábbi eljárásokat tartalmazzák:

procedure putMove(nr,label1,label2:Integer);  (Pascal)
void putMove(int nr, int label1, int label2); (C/C++)

A te lépésedet ezzel kell megadnod, azt jelenti hogy “az nr. sorból elveszed a label1 és label2 közötti sorszámú pálcikákat, a két határt is beleértve” (label1 < = label2)

procedure getMove(var nr,label1,label2:Integer);  (Pascal)
void getMove(int *nr, int *label1, int *label2);  (C/C++)

Ezzel kérdezheted le a gép válaszát, azt jelenti hogy “az nr. sorból a gép elveszi a label1 és label2 közötti sorszámú pálcikákat, a két határt is beleértve” (label1 < = label2);
Csak C/C++ esetén: azokat a változókat add meg, amelyekben az eredményt lekérdezed.

A programodnak felváltva kell hívnia a két eljárást, mindaddig, amíg van pálcika a táblán. Érvénytelen lépés esetén megszakad a program futása.

---

Bemenet:

Állomány név: STICKS.IN
1. sor: N (Egy egész szám, a pálcikákat tartalmazó sorok száma (1< = N< = 10))
2. sor: S₁ S₂ ... S_N (N egész szám, egy-egy szóközzel elválasztva, az egyes sorokban levő pálcikák száma (1< = S_i < = 10))
3. sor: X (X csak 0 vagy 1 lehet. Ha X=0, akkor neked kell először lépni, egyébként pedig a gépnek.)

Megjegyzés:

Minden tesztre létezik nyerő stratégia.

Példa:

 

STICKS.IN	Lehetséges eljáráshívás-sorozat
2 1 3 1	getMove(nr, k1, k2); -> nr=2, k1=2, k2=2 putMove(1, 1, 1); getMove(nr, k1, k2); -> nr=2, k1=1, k2=1 putMove(2, 3, 3); **** te győztél ****

Egy látképet egyenes szakaszok sorozatával adunk meg

A látkép felett N darab lámpa van, azonos T magasságban, különböző vízszintes pozíciókban. A lámpákkal szeretnénk megvilágítani a teljes látképet. A látkép egy pontja akkor van megvilágítva, ha látszik valamelyik lámpából "nézve", azaz a pontot a lámpával összekötő egyenes szakasz nem érinti a tájkép más pontját.

Feladat:

Írj programot, amely megadja a lehető legkevesebb lámpát, amelyekkel a teljes tájkép megvilágítható!

Bemenet:

Állománynév: LIGHT.IN
1. sor: M (Egy egész szám, a látkép töréspontjainak száma, beleértve az első és az utolsó pontot is.)
2..M+1. sorok: X_i H_i (Két egész szám, egy szóközzel elválasztva: az i-edik töréspont H_i magasságban, az X_i vízszintes pozíción van, 1 < = i < = M; (1 < = i < = M-1 esetén teljesül X_i+1 > X_i); egy egyenes szakaszt két egymás utáni pont ad meg.)
M+2. sor: N T (Két egész szám, egy szóközzel elválasztva, a lámpák N száma és T magassága. A lámpákat 1-től N-ig sorszámozzuk.)
M+3. sor: B₁ B₂ ... B_N (N darab egész szám, egy-egy szóközzel elválasztva: a lámpák vízszintes koordinátái (B_i+1 > B_i, 1 < = i < = N-1).)

Kimenet:

Állománynév: LIGHT.OUT
1. sor: K (Egy egész szám: a bekapcsolandó lámpák minimális száma.)
2. sor: L₁ L₂ ... L_K (K egész szám, egy-egy szóközzel elválasztva: a bekapcsolt lámpák sorszámai, növekvő sorrendben.)

Korlátok:

1 < = M < = 200
1 < = N < = 200
1 < = X_i < = 10000 minden 1 < = i < = M
1 < T < = 10000
1 < = H_i < = 10000 minden 1 < = i < = M
T > H_i minden 1 < = i < = M
X₁ < = B₁ és B_N < = X_M
Minden tesztesetre van megoldás.
Ha több megoldás is van, akkor csak egyet kell kiírni.

Példa:
 

LIGHT.IN	LIGHT.OUT
6 1 1 3 3 4 1 7 1 8 3 11 1 4 5 1 5 6 10	2 1 4