 |
Az I. 457. feladat (2018. május) |
I. 457. Egy síkon \(\displaystyle K\) darab pálcika fekszik – a Marokkó nevű játékhoz hasonlóan – melyeket pozitív egész számokkal azonosítunk. A pálcikák elhelyezkedése véletlenszerű, egymást úgy keresztezhetik, hogy a nagyobb azonosítójú van mindig feljebb. A pálcikák végpontjainak koordinátái egész számok. A pálcikák egyesével gyűjthetők össze úgy, hogy egy pálcika elvételekor a többi pálca nem mozdulhat meg: az a pálcika vehető el, amelyet felülről nem keresztez másik. Két pálcika végpontjának találkozása nem számít keresztezésnek.
Készítsünk programot i457 néven, amely a pálcikák azonosítójának egy olyan sorrendjét adja meg, amellyel a pálcikák mindegyike elvehető úgy, hogy minden lépésben az elvehető pálcikák közül a legkisebb sorszámút választjuk.
A program standard bemenetének első sorában a pálcikák \(\displaystyle K\) (\(\displaystyle 2\le K\le 50\)) számát és az ezt követő \(\displaystyle K\) sorban a pálcikák azonosítóját és végpontjainak \(\displaystyle (x_1, y_1)\) és \(\displaystyle (x_2, y_2)\) (\(\displaystyle 1\le x_{1}, y_{1}, x_{2}, y_{2} \le 50)\) koordinátáit adjuk meg. A program írja ki a standard kimenetre a pálcikák azonosítójának szóközzel elválasztott sorrendjét, amely megadja az összes pálcika elvételének megfelelő sorrendjét.
| Példa a bemenetre (a / sortörést jelöl): | Kimenet |
| 9 1 17 29 18 19 / 2 26 27 19 20 / 3 22 29 15 22 4 18 14 15 24 / 5 20 14 18 24 / 6 20 22 22 12 7 25 19 19 11 / 8 23 14 21 24 / 9 29 28 27 38 |
4 3 1 5 8 7 6 2 9 |
Beküldendő egy tömörített i457.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.
(10 pont)
A beküldési határidő 2018. június 11-én LEJÁRT.
Statisztika:
6 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Papp Marcell Miklós, Szalay Bálint, Ürmössy Dorottya, Vígh Márton. 3 pontot kapott: 1 versenyző.
A KöMaL 2018. májusi informatika feladatai