Az S. 35. feladat (2008. április)

S. 35. Adott a koordinátasíkon n darab (legföljebb 100) pont, melyek mindkét koordinátája egész szám. Szeretnénk ezek egy részét kiválasztani úgy, hogy a nem kiválasztott pontok mindegyikébe tudjunk a kiválasztott pontok legalább egyikéből egy olyan szakaszt húzni, melyre nem esik egyetlen más pont sem. Adjunk meg egy lehető legkisebb elemszámú kiválasztandó részhalmazt.

A számpárok egy szöveges állomány egymást követő soraiban találhatók, egymástól szóközzel elválasztva. A program a parancssorának első paraméterében megadott szöveges állományból olvassa be őket, majd a parancssor második paraméterében megadott szöveges állományba írja ki a bemenethez hasonló formátumban a részhalmaz pontjainak koordinátáit.

Beküldendő a program forráskódja (s35.pas, s35.cpp, ...), valamint a program rövid dokumentációja (s35.txt, s35.pdf, ...), amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

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

A megoldást adó program a következőt teszi:

1. A bemeneti állomány feldolgozása után megvizsgálja, hogy mely pontok közé húzható más pontot nem tartalmazó szakasz.

2. Megszámolja, hogy melyik pontból hány ilyen szakasz húzható, és átrendezi a pontokat csökkenő sorrendbe aszerint, hogy hány másik pont "érhető el" belőlük.

3. Ezután visszalépéses kereséssel megvizsgálja, hogy a pontok melyik részhalmaza lesz megfelelő: először az egyelemű, aztán a kételemű, stb. halmazokat veszi. A keresés mindig a legkisebb indexű, tehát legtöbb másik pontot elérő szakaszokkal indul, ezért aránylag kevés eset végignézésével talál megoldást.

Az algoritmus a következő Pascal programban (Delphi Console alkalmazás) található: s35mo.dpr.

A beküldött munkákat a következő forrásokkal teszteltük: teszt.zip , és az s35ell.dpr (szintén Delphi karakteres ablakban futó) programmal ellenőriztük.

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Weisz Ágoston.
5 pontot kapott:	2 versenyző.

A KöMaL 2008. áprilisi informatika feladatai