Az I. 394. feladat (2016. február)

I. 394. A Birodalom kutasz droidja a Felkelőket keresi Nhalo városában. A város épületei téglalap alakúak, oldalaik párhuzamosak egymással. A droidot szállító egység egy megadott épületre száll le, ahol azonnal elkezdi a keresést. Először átvizsgálja a teljes épületet, majd az épülethez legközelebbi, egyik legkisebb épületben folytatja a keresést. Egy épület átvizsgálásának ideje az épület területével egyező időegységig tart. Miután végzett egy épülettel, ismét megállapítja, hogy a jelenlegi épülethez képest melyek a legközelebbi át nem vizsgált épületek, és azok közül az egyik legkisebbel folytatja a keresést. Ha több legkisebb épület van legközelebb, akkor a kutasz a legkisebb \(\displaystyle X\) koordinátával rendelkezőt választja, illetve egyenlő \(\displaystyle X\) koordináták esetén a legkisebb \(\displaystyle Y\) koordinátával bírót. A kutasz egyik épülettől a másikig a vizsgálat idejéhez képest elhanyagolható idő alatt ér át. Az épületek közötti távolság a két épület két egymáshoz legközelebbi pontjának/pontjainak távolsága.

A Felkelők a város egy adott épületében rejtőznek. Ismerik a fürkész droid kereső algoritmusát, és látják, hogy melyik épületre szállt le. Azonnal megkezdik a felkészülést a kiürítésre, de szeretnék tudni, hogy mennyi időegység áll rendelkezésükre. Mindenképp el kell indulniuk, mielőtt a droid az épületüket eléri. Számítsuk ki, hogy legföljebb mennyi idejük van a droid megérkezéséig.

A program a standard bemenetről olvassa be a város térképének adatait, valamint a Felkelők és a kutasz droid kiindulási helyét. (A standard I/O kezeléséről több feladat megoldása kapcsán is írtunk, a leírást tartalmazó stdio.pdf fájl honlapunkon elérhető pl. az S.64. feladat megoldásának végén.) A bemenet első sorában egy pozitív érték szerepel, amely megadja az épületek \(\displaystyle P\) számát (\(\displaystyle 2\le P\le 100\)). A bemenet következő \(\displaystyle P\) számú sorában az épületek derékszögű koordináta-rendszerben adott egész koordinátái szerepelnek, melyek értékei \(\displaystyle -100\) és \(\displaystyle +100\) közöttiek. A bemenet utolsó előtti sorában a kutasz droid leszállási helye, az utolsó sorában a Felkelők épületének egyik pontjának két koordinátája szerepel. A program adja meg a standard kimenet első sorába a kiürítésig biztosan rendelkezésre álló időt, a második sorban a droid által érintett épületek átvizsgálási idejét az előbbi időtartam mellett.

Példa (amelyben az újsor karakterek egy részét a tömörség kedvéért / jellel helyettesítettük):

Beküldendő egy tömörített i394.zip állományban a program forráskódja és rövid dokumentációja, amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2016. március 10-én LEJÁRT.

A beküldött megoldásokat a következőkkel teszteltük: i394teszt.zip Bár a feladat szövege nem mondta ki, hogy a koordináták bal-alsó, jobb felső sorrendben vannak, de a mintapélda alapján minden versenyző ezt feltételezte, így ilyenek a tesztfájlok is.

Az eredeti mintapélda kimenete valóban helytelen, elnézést kérünk, a honlapon kijavítjuk.

Mintamegoldásként Olexó Gergely 11-edikes, budapesti versenyző C# nyelven készült munkáját mutatjuk be: i394.cs

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Hamrik Szabin, Kovács 246 Benedek, Nagy Ábel, Olexó Gergely.
7 pontot kapott:	1 versenyző.

A KöMaL 2016. februári informatika feladatai