Az S. 125. feladat (2018. április)

S. 125. Egy bolygó felszínét teljesen lefedik a rajta található országok, melyeket egymástól határvonalak választanak el. Minden ország egy-egy összefüggő részén található a bolygónak. A határvonalak a bolygó felületén haladó görbék, találkozási pontjaikban határvárosok találhatók. Egy-egy határváros legalább kettő, de akár több ország határvonalainak a találkozási pontja. Minden országnak legalább két szomszédja, és legalább három határvárosa van. A határvonalak a határvárosokon kívül nem keresztezik egymást, és határváros sincs máshol, csak határvonalak találkozásánál.

Egy ország határvárosainak számát nevezzük az ország határszámának. Állapítsuk meg, hogy mennyi a bolygón az országok határszámának maximuma.

A határvárosokat pozitív egész számokkal, a határvonalakat a megfelelő határvárosok számából képzett számpárokkal jelöljük. A megoldást adó program a standard bemenet első sorából olvassa be a határvárosok \(\displaystyle V\) számát, illetve a határvonalak \(\displaystyle L\) számát, majd a következő \(\displaystyle L\) sor mindegyikéből egy-egy határvonalat megadó számpárt. A program írja a standard kimenetre a bolygón található országok határszámai közül a legnagyobbat.

Példa:

Korlátok: \(\displaystyle 4\le V\le 1000\).

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb bemeneti értékek esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy s125.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(10 pont)

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

Statisztika:

1 dolgozat érkezett.
2 pontot kapott:	1 versenyző.

A KöMaL 2018. áprilisi informatika feladatai