Nemzetközi Informatikai Olimpia 2000

Peking, Kína



Autóparkoló - 1. Nap, 1. feladat (  pont, időlimit:   mp tesztesetenként) /tesztadatok/
A NAGY FAL parkolóban N egymás mögötti parkolóhelyen N, nem feltétlenül különbözö típusú autó parkol. A típusokat 1 és M közötti egész számokkal adjuk meg. W számú munkás típusszám szerint rendezi növekvö sorrendbe az autókat az alábbi elven: Egy ún. körben minden munkás (egyszerre) kivihet egy autót a parkolóból, amit az így keletkezett legfeljebb W üres hely valamelyikére visz vissza. Lehetséges, hogy egyes körökben nem minden munkás mozgat autót. A cél a rendezettség elérése minél kevesebb körben.

Írj programot, amely adott autósorrendre megad egy rendezést maximum [N/(W-1)] (azaz N/(W-1) felfelé kerekítve) lépésben. A minimálisan szükséges körök száma biz-tosan nem nagyobb ennél az értéknél.

Például legyen 10 autónk, melyek típusa 1, 2, 3 vagy 4 lehet, és legyen 4 munkásunk. Az autók eredeti sorrendje:

2 3 3 4 4 2 1 1 3 1.
A minimálisan szükséges körök száma 3, az autók sorrendje az egyes körök után például a következö lehet:
2 1 1 4 4 2 3 3 3 1 – az 1. kör után,
2 1 1 2 4 3 3 3 4 1 – a 2. kör után, és
1 1 1 2 2 3 3 3 4 4 – a 3. kör után.
Bemenet:
A CAR.IN állomány elsö sorában három egész szám van egy-egy szóközzel elválasztva: az autók száma (2 <= N <= 20000), az autótípusok száma (2 <= M <= 50) és a munkások száma (2 <= W <= M). Minden típushoz legalább 1 autó tartozik. A második sorban N egész szám van egy-egy szóközzel elválasztva: az i-edik szám az i-edik helyen álló autó típusa.
Kimenet:
A CAR.OUT állomány elsö sorába azt kell írni, hogy a megoldásod hány körböl (R) áll. A következö R sor az egyes köröket írja le a végrehajtásuk sorrendjében. Minden sorban az elsö egész szám (C) a mozgatandó autók száma, amelyet C számpár követ. Két egymás utáni egész szám azt írja le, hogy az autót honnan (a pár elsö tagja) hova (a pár második tagja) kell mozgatni. Több, ugyancsak R körböl álló megoldás is lehet, de közülük csak egyet kell megadni.
Példa:
 
CAR.IN CAR.OUT
10 4 4
2 3 3 4 4 2 1 1 3 1
3
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1

Részpontszámok:

Legyen Q=[N/(W-1)] . Ha a programod által megadott R kör leírása hibás vagy a program nem jól rendez, akkor a pontszámod 0 lesz. Jó megoldás esetén a pontszámod így számolják ki a maximális pontszámból:

R <= Q   100%
R = Q+1   50%
R = Q+2   20%
R >= Q+3   0%
 



Palindrom - 1. Nap, 2. feladat (  pont, időlimit:   mp) /tesztadatok/
A palindrom egy szimmetrikus karaktersorozat, azaz balról jobbra és jobbról balra olvasva azonos. Írj programot, amely egy adott karaktersorozathoz megadja a minimálisan beszúrandó karakterek számát, úgy hogy az eredmény palindrom legyen!

Például 2 karakter beszúrásával az “Ab3bd” karaktersorozat palindrommá alakítható (“dAb3bAd” vagy “Adb3bdA” is lehet belöle). Kettőnél kevesebb karakter beszúrásával azonban ebből a karaktersorozatból nem állítható elő palindrom.

Bemenet:

A PALIN.IN állomány elsö sorában a bemenő karaktersorozat hossza, N (3 < = N < = 5000), a második sorban egy N hosszúságú karaktersorozat (string) van. A karaktersorozat az angol ábécé kis- és nagybetűiből, valamint számjegyekből állhat. A kis- és a nagybetűket megkülönböztetjük.
Kimenet:
A PALIN.OUT állomány egyetlen sorába egyetlen egész számot ( > = 0), a keresett minimális értéket kell írni.
Példa:
 
palin.in palin.out
5
Ab3bd
2


Median Strength - 1. Nap, 3. feladat (  pont, időlimit:   mp) /tesztadatok/
Egy űrkísérletben N tárgyat használunk, melyeket 1-töl N-ig számozunk, ahol N páratlan. Minden tárgy különböző súlyú (természetes számok), de magukat a súlyokat nem ismerjük. Minden Y súlyra igaz, hogy 1 < = Y < = N. Mediánnak nevezzük azt a tárgyat, amelyiknél ugyanannyi könnyebb, mint nehezebb tárgy van. Írj programot, amely meghatározza a mediánt! A tárgyak súlyát olyan eszközzel hasonlíthatjuk össze, amely három tárgy közül megadja a mediánt.

Könyvtár:

A device nevű könyvtárból az alábbi három művelet használható: A device könyvtár függvényei két szöveges állományt hoznak létre MEDIAN.OUT és MEDIAN.LOG néven. A MEDIAN.OUT elsö sorában egy egész szám lesz, az, amit az Answer eljárásnak adtál át. A második sorban a Med3 hívások száma lesz. A programod és a könyvtár közötti párbeszédet a MEDIAN.LOG tartalmazza.
Pascal programozóknak:
programodba írd be a következő sort:
uses device;
Kipróbálás:
Programod kipróbálásához készíts DEVICE.IN néven olyan állományt, amely két sorból áll. Az elsőbe a tárgyak számát (N) kell írni. A második sor a tárgyak súlyát (1 és N közötti különböző egész számok) tartalmazza, ahol az i-edik érték az i-edik tárgy súlya.
Könyvtár:
A device nevü könyvtárból az alábbi három művelet használható:
Példa:
 
DEVICE.IN
5
2 5 4 3 1
Ez az állomány a következő esetet írja le
 
Sorszám 1 2 3 4 5
Súly 2 5 4 3 1
Ebben az esetben a helyes hívási sorrend:
1. GetN értéke 5.
2. Med3(1,2,3) értéke 3.
3. Med3(3,4,1) értéke 4.
4. Med3(4,2,5) értéke 4.
5. Answer(4)
Kikötések: