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. 82. feladat (2013. szeptember)

S. 82. Adott egy N×N-es sakktábla, és N (N\le 1\;000\;000) darab bástya. El szeretnénk helyezni őket a sakktáblán úgy, hogy semelyik kettő ne üsse egymást. Két bástya akkor és csak akkor üti egymást, ha egy oszlopban, vagy egy sorban vannak. Ez így nagyon egyszerű lenne, de vannak megkötéseink: az i. bástyát csak az (ai,bi) bal felső, és (ci,di) jobb alsó koordinátájú téglalapba helyezhetjük. Az a kérdés, hogy megoldható-e ez? Ha nem, írjuk ki, hogy NEM, ha megoldható, akkor adjunk is meg egy megoldást: minden bástya sor, illetve oszlopkoordinátáit írjuk ki külön sorba. A bástyák elhelyezését olyan sorrendben kell kiírni, amilyenben a téglalapok voltak, tehát az első sorba az első bástya koordinátái kerüljenek.

A program olvassa be a standard input első sorából N-et, majd a következő N sorból az ai, bi, ci, di szóközzel elválasztott egészeket, és írja a standard output első sorába a NEM szót, vagy pedig a bástyaelhelyezéseket.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. A megoldáshoz weboldalunkon találhatóak példa be- és kimenetek, amelyekkel érdemes letesztelni a programot.

Részpontszámok a következőkre kaphatóak:

- a program N\le12-re megoldást ad;

- minden téglalap 1×2-es, vagy 1×3-as;

- minden téglalap 1×2-es, vagy 2×2-es.

Beküldendő egy tömörített s82.zip állományban a program forráskódja (s82.pas, s82.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s82.txt, s82.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

Tesztbemenetek letöltése: teszt.zip

(10 pont)

A beküldési határidő 2013. október 10-én LEJÁRT.


Mintamegoldásként és hozzá dokumentációként Fonyó Viktória megoldását tesszük közzé: S82.zip


Statisztika:

13 dolgozat érkezett.
10 pontot kapott:Fonyó Viktória, Jákli Aida Karolina, Somogyvári Kristóf, Weisz Ambrus.
7 pontot kapott:1 versenyző.
6 pontot kapott:1 versenyző.
5 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
3 pontot kapott:2 versenyző.
2 pontot kapott:1 versenyző.
1 pontot kapott:2 versenyző.

A KöMaL 2013. szeptemberi informatika feladatai