Nemzetközi Informatikai Olimpia 1997

Cape Town, Dél-Afrika



Karakterfelismerés - 2. Nap, 1. feladat (# pont, időlimit: # mp)
Egy olyan programot kell írnod, amely alkalmas karakterfelismerésre.

Feladatleírás:

Minden ideális karakterkép 20 sorból áll, soronként 20 számjeggyel. A számjegyek 0-k vagy 1-ek lehetnek. Az 1a ábrán karakterek képe látható file-ban.

A FONT.DAT állomány tartalmazza a 27 karakter ideális képét az alábbi sorrendben:
_abcdefghijklmnopqrstuvwxyz
ahol _ a szóköz karaktert jelöli.

Az IMAGE.DAT állomány egy vagy több, esetleg sérült karakter képét tartalmazza. A karakter képe az alábbi módokon lehet sérült:

Nincs olyan karakterkép, amelyben egy sor duplán szerepel, egy másik pedig hiányzik. Egy karakterképben legfeljebb a ‘0’-k és az ‘1’-esek 30%-a sérült.

Sorismétlés esetén mindkét sorban lehetnek sérült számjegyek, mégpedig a két sorban esetleg különbözôképpen.

Feladat:
Készíts programot, amely az IMAGE.DAT állományban adott sérült karaktersorozatot felismeri, a FONT.DAT állományt felhasználva.

Egy karakter felismerhetô a FONT.DAT állományban levô karakterképek alapján, azaz a program azt ismeri fel, amelyikre a legjobban hasonlít (amelybôl esetleges sorismétlés vagy törlés után a lehetô legkevesebb ‘1’-es és ‘0’-s megváltoztatásával kapható). Sorismétlés esetén azt kell számolni, amelyikben a kevesebb sérülés van.

Egy jól megírt programmal a tesztfile-okban szereplô karakterek mindegyike egyértelműen felismerhetô.

Egy korrekt megoldás az IMAGE.DAT állomány minden adatát felhasználja.
 

Bemenet:
Mindkét bemenô állomány elsô sorában az N egész  szám van (19 <= N <= 1200): a további sorok száma.
 
N
(digit1)(digit2)(digit3) ... (digit20)
(digit1)(digit2)(digit3) ... (digit20)
...

Minden sor 20 számjegyet tartalmaz, melyek között nincs szóköz.

A FONT.DAT állomány a karakterek ideális képét tartalmazza, amely mindig 541 sorból áll. Ez az állomány az egyes teszteknél különbözô is lehet.

Kimenet:
A programod készítse el az IMAGE.OUT állományt, amely egyetlen sorban tartalmazza a felismert karaktereket. A karakterek közé nem lehet elválasztó jelet (pl. szóközt) tenni. Ha a programod nem ismer fel egy karaktert, akkor az eredménybe, a megfelelô helyre, a karakter helyett a ? karaktert kell írnia.
Példa:
 
FONT.DAT
(részlet)
IMAGE.DAT IMAGE.OUT
540
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000011100000000000
00000111111011000000
00001111111001100000
00001110001100100000
00001100001100010000
00001100000100010000
00000100000100010000
00000010000000110000
00000001000001110000
00001111111111110000
00001111111111110000
00001111111111000000
00001000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
19
00000000000000000000
00000000000000000000
00000000000000000000
00000011100000000000
00100111011011000000
00001111111001100000
00001110001100100000
00001100001100010000
00001100000100010000
00000100000100010000
00000010000000110000
00001111011111110000
00001111111111110000
00001111111111000000
00001000010000000000
00000000000000000000
00000000000001000000
00000000000000000000
00000000000000000000
a
Pontozás:
A pontszám a helyesen felismert karakterek százalékától függ.


Térkép címkézése - 2. Nap, 2. feladat (# pont, időlimit: # mp)
Térképész-asszisztens vagy, és azt a feladatot kaptad, hogy egy új térképre írd fel a városok nevét.
A térkép olyan rács, amely 1000x1000 cellából áll. Minden város egyetlen cellát foglal el a térképen. A városneveket cellákból álló téglalap alakú dobozokba kell írni a térképen. Az ilyen dobozt címkének hívjuk.


Egy város, és a városhoz tartozó címke négy lehetséges helyzete

A címkék elhelyezésének ki kell elégítenie a következő feltételeket:

1. A városhoz tartozó címkét a városhoz képest négyféleképpen lehet elhelyezni, amint azt az 1. ábra mutatja.
2. A címkék nem lehetnek egymással átfedésben.
3. A címkék nem takarhatják el a városokat.
4. A címkéknek teljes egészükben el kell férniük a térképen.
Minden egyes címkének tartalmaznia kell a városnév összes betűjét, valamint a városnév előtt vagy mögött egyetlen szóközt. Minden egyes városnévhez megadjuk betűinek szélességét és magasságát; a szóköz mérete megegyezik a betűkével.


Az üres négyzet szóközt jelöl, a teli négyzet pedig egy várost.

A térkép bal szélső oszlopának 0 a vízszintes, alsó sorának pedig 0 a függőleges indexe. A 2. ábrán egy térkép bal alsó részlete látható, három város adataival: Langa a (0,3), Ceres a (6,1), Paarl pedig a (7,3) pozícióban található. A címkék elhelyezése szabályos a térképen, de nem ez az egyetlen szabályos elhelyezés.

Feladat:

A programnak be kell olvasnia a városok helyének koordinátáit, majd a betűinek méretét, és végül a nevét. A programnak ezután a lehető legtöbb címkét kell felraknia a térképre anélkül, hogy a fenti feltételeket megsértené, majd ki kell írnia a felrakott címkék adatait.
Bemenet:
A bemeneti állomány első sorában egy egész szám (N) van, amely a térképen található városok számát adja meg. Minden városhoz egy-egy sor tartozik a bemeneti állományban, öt-öt adattal: Minden városnév egyetlen szó. A városok száma legfeljebb 1000. A városnév legfeljebb 200 betűbôl áll.
Kimenet:
A programodnak N sort kell kiírnia. Minden sorba egy-egy város címkéje bal felső sarkának vízszintes és függőleges indexét kell kiírni, ebben a sorrendben. Ha a programod valamelyik város címkéjét nem tudja felrakni a térképre, akkor a –1 –1 sorozatot kell kiírnia. A sorokat abban a sorrendben kell kiírni, amilyen sorrendben a városok a bemeneti állományban szerepelnek. A két szám közé egyetlen szóközt kell tenni.
Példa:
 
MAPS.DAT MAPS.OUT
3
0 3 1 1 Langa
6 1 1 1 Ceres
7 3 1 2 Paarl
1 4
0 0
8 2
Pontozás:
Minden egyes tesztadat-készletre


Konténertárolás - 2. Nap, 3. feladat (# pont, időlimit: # mp)
A Neptune Cargo Company egy konténertárolót üzemeltet, ami konténereket fogad, tárol, majd a késöbbiekben kiad.

Minden órában, pontban egészkor,  pontosan egy konténer érkezik, és pozitív egész számú óráig marad a tárolóban. Amikor egy konténer megérkezik, a kisérőlevél tartalmazza a kiadás várható idejét. Az első konténer az első órában érkezik. A tényleges időpont, amikor a konténert ki kell adni, a várható időpontot legfeljebb 5 órával előzheti vagy haladhatja meg.

Az idő pozitív egész szám, amely legfeljebb 150-ig növekszik.

A tároló felett egy mozgódaru működik, amely a konténereket ki- és beviszi a tárolóba, illetve olykor átrendezi azokat. A mozgódaru számára mindig van elegendô hely a konténerek felett.

Feladat:

Írj programot, amely jó stratégiát valósít meg a konténerek tárolására és kiadására. Az a stratégia jobb, amely kevesebb számú mozgatással oldja meg feladatát.
A tároló egy téglatest alakú tér, amelynek hossza (X), szé-les-sége (Y) és magassága (Z) elérhetô a program számára.
A konténerek 1x1x1-es kockák. A konténerek egymás tetejé-re, illetve a padlóra helyezhetôk. A mozgódaru csak az adott oszlop legfelsô konténerét mozgathatja el.

Egy konténer áthelyezése egy tetszőleges helyről egy tetszőleges helyre mindig mozgatási műveletnek számít. A belső mozgatások nem vesznek igénybe időt.

Amikor a tároló megtelik, programod köteles visszautasítani újabb konténerek bevitelét. Ugyanakkor programod hatékonysága lecsökkenhet, vagy akár folytatásra képtelenné válhat, ha a tároló majdnem tele van. Ezért bármikor visszautasíthatod az új konténer bevitelét, de ez pontveszteséggel jár.

Bemenet:
Programod egy szimulációs modul függvényeire és eljárásaira építve szerzi meg az adatokat, s manipulálja azokat. A tároló kezdetben üres.
A program fejlesztése alatt a modul értelmes adatokat fog szolgáltatni, de csak egy rögzített, kisméretű bemenetre.
Minden konténernek egyedi azonosítója van, egy pozitív egész szám.

Programod bármikor meghívhatja az alábbi függvényeket:
 

function GetX: integer; Visszaadja a tároló hosszát (X).
function GetY: integer; Visszaadja a tároló szélességét (Y).
function GetZ: integer; Visszaadja a tároló magasságát (Z).

X,Y,Z legfeljebb 32 lehet.

A következö függvények a tevékenységsorozatról (konténer érkezése, kiadásának kérése) adnak információt. Az érkezés minden egész órakor, a kiadások kérése óra közben történik. Két érkezés között több kiadáskérés is elöfordulhat. Ezért az idö nyilvántartása szempontjából az érkezések jelölik az idö múlását.
 

function GetNextContainer: integer;
Egy pozitív egész számot ad vissza, mégpedig a következö konténer azonosítóját,
amit tárolni vagy kiadni kell. Ha már nincs további, konténerre vonatkozó kérés, 
akkor az eredmény 0, ami azt jelenti, hogy programodnak 
be kell fejezödnie még akkor is, ha vannak konténerek a tárolóban.

 
function GetNextAction: integer;
A következö végrehajtandó tevékenységet határozza meg: 
1, ha tárolni kell, 2, ha kiadni kell a konténert.

 
function GetNextStorageTime: integer;
Visszaadja a konténer várható kiadási idejét órákban, a kezdettöl számítva. 
Ez az érték csak tervezési célokat szolgál, a tényleges kiadási kérés 
ettől különbözö is lehet, de legfeljebb öt órával térhet el ettől. 
A függvény csak akkor ad értelmes értéket, ha a GetNextAction 1-t ad vissza.

A fenti három függvény hívásának sorrendje tetszöleges lehet.

A GetNextContainer, GetNextAction és GetNextStorageTime függvények egymás utáni többszöri hívása ugyanarra a konténerre vonatkozó adatokat adja vissza, amíg az adott konténer visszautasításra, tárolásra vagy kiadásra nem kerül, amikor a fenti függvények értékei már a következö konténerre vonatkoznak.

Kimenet:
Miután programod meghatározta a következö konténerre vonatkozó szükséges információkat, a következö függvényeket kell használnod a tároló állapotának módosítására:
 
function MoveContainer(x1, y1, x2, y2: integer): integer;
Az x1,y1 pozíción levö legfelső konténert átmozgatja az x2,y2 pozíciójú oszlop tetejére.
1-t ad vissza, ha a művelet érvényes, 0-t ha nem (azaz ha lehetetlen).

 
procedure RefuseContainer;
Visszautasítja az érkezö konténer tárolását.

 
procedure StoreArrivingContainer(x, y: integer);
Eltárolja az érkezö konténert az x,y-nal megadott oszlop tetején.

 
procedure RemoveContainer(x, y: integer);
Kiadja az x,y-nal meghatározott oszlop tetején levö konténert.

Ha programod nem tudja végrehajtani a kért tevékenységet, be kell fejeződnie.

Az illegális mozgatásokat a modul figyelmen kívül hagyja, és nem befolyásolja a tároló állapotát, továbbá nem számítanak bele a pontozásba.

Programodnak nem szabad írni semmifajta file-ba, ugyanis a modulbeli függvények és eljárások elvégeznek minden adminisztrációt. Ennek során egy file jön létre, amit a kiértékelés során fognak fölhasználni.

Végrehajtási sorrend:
Programodnak elöször információt kell szereznie a következő konténerre vonatkozó kérésröl. Ezután, ha szükséges, átrendezheti a tárolót. Majd el kell tárolni, vagy vissza kell utasítani, illetve ki kell adni a konténert.
Modul:
A szimulációs modult StackLib-nek hívják, és hozzá kell linkelni a programkódhoz. Minta forrásfile-ok a feladatkönyvtárban találhatók a következö néven: TESTSTK.PAS, TESTSTK.CPP és TESTSTK.C.
Pontozás:
A program különbözö adathalmazokra lesz tesztelve, s a pontszám az általunk ismert legjobb megoldáshoz lesz viszonyítva az alábbiak szerint: