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 S. 161. feladat (2022. április)

S. 161. Egy épület különböző pontjaira vizet kell vezetni. Az épület tervrajzán \(\displaystyle N\) darab pont mutatja ezeket a helyeket. A tervrajzra gondolatban egy koordináta-rendszert illesztünk, amelyen az \(\displaystyle N\) pont mindegyike egész koordinátákra esik. A vezetékeket úgy építik, hogy a pontokat összekötik egyenes csövekkel úgy, hogy bármelyikből bármelyik másikba el lehessen jutni a csöveken haladva. A merev csöveket csak a tervrajzon jelölt pontokban tudjuk elágaztatni és nem is keresztezhetik egymást. Minden cső a koordináta-rendszer egy-egy rácsvonalára kerül és két megadott pontot köt össze. Adjuk meg, hogy legalább milyen hosszú lesz a csővezetékek hossza, ha közvetetten bármely két pontot összekötjük.

Bemenet: az első sor tartalmazza a pontok \(\displaystyle N\) számát. A következő \(\displaystyle N\) sor mindegyike egy-egy pont \(\displaystyle x\) és \(\displaystyle y\) koordinátáját tartalmazza.

Kimenet: a kimenet első és egyetlen sorába a csövek lehető legkisebb összhosszát kell kiírni. Ha nem lehet őket mind összekötni, akkor -1-et kell kiírni.

Minta:

Bemenet (a / jel sortörést helyettesít)Kimenet
6 / 0 2 / 0 3 / 1 0 / 1 3 / 2 2 / 2 3 7

Korlátok: a koordináták abszolút értéke legfeljebb 1000 és \(\displaystyle N \le 30\). Időlimit: 0,5 mp.

Értékelés: a pontok 30%-a kapható, ha az \(\displaystyle x\) koordináta 0 vagy 1 értéke esetén a program helyes kimenetet ad.

Beküldendő egy s161.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2022. május 16-án LEJÁRT.


Statisztika:

4 dolgozat érkezett.
10 pontot kapott:Sándor Péter.
3 pontot kapott:2 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2022. áprilisi informatika feladatai