Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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