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

Zadar, Horvátország


Katonák - 2. Nap, 1. feladat (30 pont, időlimit: 10 mp)
Gridland ország N katonája véletlenszerűen helyezkedik el az ország területén négyzetrácsos szerkezetben. Minden pozició az (x,y) egész koorditátáival adható meg. Egy helyen egyszerre csak egy katona tartózkodhat.
A katonák úgy mozoghatnak, hogy egyszerre csak egy mozdulhat egy egységet fe, fel, balra vagy jobbra. (Tehát vagy az x vagy az y koordinátája változhat 1 vagy –1 értékkel.
A parancsnok elrendelte, hogy a katonák egy vizszintes sorba (x tengely) rendeződjenek, tehát a poziciójuk (x,y), (x+1,y), ..., (x+N-1,y) legyen valamely x és y értékekre. Az x és az y érték, valamint a katonák sorrendje tetszőleges lehet.
Az a cél, hogy a parancsot úgy teljesitsék, hogy a mozgások összes száma minimális legyen.
Bármely helyen egyidőben egyszerre csak egy katona tartózkodhat.

Bemenet:

A SOLDIERS.IN szöveges bemeneti állomány első sora a katonák N (1<=N<=10000) számát tartalmazza.
Az állomány következő N sorának mindegyike egy katona kezdeti helyét adja meg. Az (i+1) –edik sorban egy szóközzel elválasztva egy egész számpár van, x[i] és y[i] (-10000<=x[i],y[i]<=10000), az i–edik katona kezdeti poziciója.
Kimenet:
A SOLDIERS.OUT kimenő állomány első sorába kell irni azon összmozgasok minimális számát, amely szükséges ahhoz, hogy a katonák egy sorba rendeződjenek.
Példa:
 
SOLDIERS.IN SOLDIERS.OUT
3
1 0
2 4
3 2		 4
5
1 2
2 2
1 3
3 -2
3 3		 8

Utak - 2. Nap, 2. feladat (30 pont, időlimit: 10 mp)
Adott N város, amelyek egyirányú utakkal vannak összekötve. Minden utnak két paramétere van, az ut hossza, és az uthasználati dij (forintban kifejezve). A városokat az 1..N számokkal azonositjuk.
Alice és Bob az 1 városban lakik. Bob szakitott Alicével, mert az csalt a kártyajátékban. Elhatározta, hogy elköltözik az N városba. Az utazásra adott összeg áll rendelkezésére, ennél többet nem költhet az útra.
Ezért Bob arra törekszik, hogy a legrövidebb uthosszúságú olyan uton haladjon az 1 városból az N városba, amit még meg tud fizetni.

Bemenet:

A ROADS.IN szöveges bemenő állomány első sora az utazásra forditható pénz K (0<=K<=10000) összegét tartalmazza.
A második sorban a városok N (2<=N<=100) száma áll.
A harmadik sor tartalmazza az utak R (1<=R<=10000) számát.
A további R sor mindegyike négy egész számot, S, D, L ,T tartalmaz egy szóközzel elválasztva, ami egy ut adatai. Ezek jelentése a következő: Megjegyzendő, hogy két város között több út is lehet.
Kimenet:
A ROADS.OUT kimenő szöveges állomány első és egyetlen sora egy legrövidebb úthosszúsúgú olyan út hosszát tartalmazza, amelyen haladva az 1 városból az N városba az úthasználati díjak összege nem haladja meg a K forintot.
Ha nem létezik ilyen út, akkor –1 értéket kell irni az állomány első sorába.
Példa:
 
ROADS.IN ROADS.OUT
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2		 11
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0		 -1

Labda - 2. Nap, 3. feladat (40 pont, időlimit: 10 mp)
Balltazár professzor nagy futbalrajongó, ezért születésnapjára olyan játékot kapott, amellyel kedvére játszhat a Világbajnokság unalnas meccsein.
A játékszer futballabdára hasonlit, 12 egyenlő oldalú ötszöglap határolja, az ötszöglapok 1 től 12-ig vannak számozva. Lásd a mellékelt játékszert.
Minden oldalon van egy ötszögletű forgatható tárcsa, amelyeket szintén 1 től 12-ig számozták (ezek számozása nincs feltüntetve a játékon). A tárcsák mind az öt éle egy-egy számot tartalmaz az {0, 1, 2}halmazból. Minden tárcsa kiemelhető a helyéről és áthelyezhető bármely masik oldalra. Próbáld ki. Ha kiemeled a tárcsát, láthatod az adott oldal sorszámát. Láthatod, hogy minden tárcsa a középpontja körül elforgatható öt különböző pozicióba.

A játék célja az, hogy a tárcsákat úgy rakjuk az oldalakra, hogy alkalmasan elforgatva őket bármely két tárcsa két szomszédos (érintkező) éle azonos számot tartalmazzon.

Bemenet:

A BALL.IN bemenő szöveges állomány 12 sort tartalmaz. Minden sorban öt szám van.  Az i-edik sorban az i-edik tárcsa öt oldalán található számok vannak felsorolva óramutató bejárásban. A felsorolásban első helyen álló szám az úgynevezett referencia oldalol lévő szám.
Kimenet:
A kimenő BALL.OUT szöveges állomány pontosan 12 sort tartalmazzon, ha van a feladatnak megoldása. Ekkor minden sorban két egész szám álljon egy szóközzel elválasztva, az i-edik sorban a t[i] és az n[i] számok. t[i] a labda  i-edik oldalára rakott tárcsa (inputbeli ) sorszáma, n[i] pedig az oldalra helyezett tárcsa helyzetét mondja meg. Minden tárcsa öt különböző pozicióban rakható fel. A megoldásbeli poziciót az n[i] érték adja meg, a következőképpen:
A t[i] tárcsát úgy helyeztük fel a labda  i-edik oldalára, hogy a tárcsa referencia oldala az i -vel és n[i] –vel azonositott (szomszédos) labdaoldalak közös ötszögoldala felé van forgatva.
Ha nincs megoldás, akkor a kimenő állomány egyetlen sora a –1 értéket tartalmazza.
Példa:
 
BALL.IN BALL.OUT
0 0 1 1 2
0 2 1 0 1
2 0 1 0 1
0 0 1 2 1
0 2 1 1 2
2 0 1 2 1
0 2 1 2 1
2 2 1 0 1
1 2 2 0 0
0 2 1 0 2
0 2 1 2 0
2 0 1 2 0		 1 2
3 7
12 4
7 9
9 1
11 8
8 2
4 6
5 4
2 12
6 3
10 7
1 0 2 0 2
2 2 2 1 2
1 1 0 0 0
1 1 0 2 1
2 1 1 1 1
1 2 2 1 1
2 1 2 2 1
2 2 0 1 0
0 1 2 1 2
2 2 1 0 0
1 2 0 2 0
2 2 2 0 1		 1 2
2 7
8 2
7 1
11 4
12 2
5 2
3 12
10 5
9 3
6 10
4 7