Nemzetközi Informatikai Olimpia 1999

Antalya, Törökország



Közlekedési lámpák - 2. Nap, 1. feladat (  pont, időlimit: 2 mp)
Dingilville városában szokatlan módon működnek a közlekedési lámpák. Bármely két csomópontot legfeljebb egy (kétirányú) utca köt össze egymással. Nincs olyan utca, amely egy csomópontot önmagával kötne össze. Minden csomópontban egyetlen közlekedési lámpa van, amelyik vagy kéket (B, blue), vagy pirosat (P, purple) mutat. A lámpák színe periodikusan vált; a kék és a piros jelzés ideje különböző lehet. Egy jármű csak akkor indulhat el az egyik csomópontból a másikba, ha az elindulás pillanatában mindkét csomópontban azonos színű a lámpa. Ha egy jármű a váltás pillanatában érkezik egy csomópontba, akkor a továbbhaladáshoz már a lámpa új színét kell figyelembe venni. A jármű a csomópontoknál várakozhat. A várostérkép a következőket tartalmazza: Határozd meg a (közlekedés megindulásától számított) legrövidebb ideig tartó utat (csomópontok sorozataként) adott kezdő és célcsomópont esetén.
Ha több megoldás van, közülük csak egyet kell megadni.

Feltételek:

Bemenet:
A lights.inp szöveges állomány tartalma:
Kimenet:
A lights.out szöveges állomány tartalma:
Példa:
 
LIGHTS.IN LIGHTS.OUT
1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
127
1 2 4


Kiegyenlítés - 2. Nap, 2. feladat (  pont, időlimit: 3 mp)
Egy játékban N oszlopban egymásra rakunk korongokat (ld. az 1. ábrát). Egy mozgatást az oszlop p sorszámával és egy k számmal adunk meg. Ez azt jelenti, hogy a p-edik oszlopról k db korongot teszünk át a szomszédos (p-1)-edik és (p+1)-edik oszlopra, ha 1 < p < N-1. Az 1. oszlopról csak a 2.-ra teszünk át k db korongot, az N-edikről pedig csak az (N-1)-edikre, ugyancsak k db korongot (ld. az 2. ábrát). A művelet csak akkor végezhető el, ha az adott oszlopon elegendő számú korong van, azaz legalább 2k, ha az oszlopnak két szomszédja van, egyébként k.
 
5 oszlop 0, 7, 8, 1 és 4 koronggal Ugyanazok a  p=2, m=2 mozgatás után

A játék célja az, hogy minden oszlopra azonos számú korong kerüljön minél kevesebb mozgatással.

Feltételek:

Bemenet:
A flat.inp szöveges állomány két sort tartalmaz:
Kimenet:
A flat.out állomány első sorába a mozgatások M számát kell írni. A további M db sor mindegyikébe egy-egy mozgatást leíró két egész szám (p, k) kerüljön, mégpedig a mozgatások végrehajtásának sorrendjében.
Példa:
 
 
FLAT.INP FLAT.OUT
5
0 7 8 1 4
5
5 2
3 4
2 4
3 1
4 2
Értékelés:
A megoldásra akkor jár tesztesetenként a teljes pontszám (A), ha a mozgatások száma (x) nem haladja meg az elviselhető minimumot (B). (Megjegyzés: nem biztos, hogy B az optimum. B értéke tesztesetenként változik, és az értéke két dologtól függ: egyrészt egy egyszerű stratégiát alkalmazó kiegyenlítéshez szükséges mozgatások redundancia-mentes számától, másrészt a korongok kezdeti eloszlásától.) A pontszámot kerekítéssel határozzuk meg az alábbi képlet szerint:
A,               ha x <= B
2A*(1,5*B–x)/B,  ha B < x < 1,5*B
0,               ha x >= 1,5*B


Leszállópálya - 2. Nap, 3. feladat (  pont, időlimit: 60 mp)
Dingilville városa repülőteret épít. Az építésre kijelölt terület térképe téglalap alakú négyzetrács, amely a mezők tengerszint feletti magasságát is feltünteti. A mezőket vízszintes (kelet-nyugati irányú) x és függőleges (észak-déli irányú) y koordinátájuk azonosítja.

Határozd meg azt a legnagyobb, azaz a legtöbb mezőt tartalmazó téglalap-alakú területet, amelyre az alábbi két feltétel teljesül:

a) a legmagasabban és a legalacsonyabban fekvő mező tengerszint feletti magasságának különbsége nem haladja meg a C korlátot,
b) a téglalap oldalának hossza kelet-nyugati irányban legfeljebb 100 egység.
Feltételek:
Bemenet:
A land.inp állomány
Kimenet:
A land.out szöveges állomány egyetlen sorába négy egész számot kell írni, ahol az első két szám a téglalap-alakú terület délnyugati, a második kettő pedig az északkeleti sarkán fekvő mező (x,y) koordinátája.
Példa:
 
LAND.INP LAND.OUT
10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41
4 5 8 11



 
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41