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/S. 5. feladat (2016. január)

I/S. 5. Adott (\(\displaystyle 1 \le N \le 1\;000\;000\)) db, kezdetben üres doboz, ahol \(\displaystyle N\) páratlan egész. Egy lépésben néhány szomszédos dobozba beleteszünk egy-egy kavicsot. Adott (\(\displaystyle 1 \le K \le 25\;000\)) db lépés, mindegyik lépés leírása két számot tartalmaz: \(\displaystyle x\), \(\displaystyle y\) (\(\displaystyle x\le y\)). Ennek jelentése: az \(\displaystyle x\). doboztól az \(\displaystyle y\). dobozig minden dobozba teszünk még egy kavicsot. Ezek után az \(\displaystyle N\) doboz kavicsai számának mediánjára vagyunk kíváncsiak. Valahány páratlan szám mediánja a növekvő sorrendbe rendezett számsorból a középső elem.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle K\)-t, majd a következő \(\displaystyle K\) sorból az \(\displaystyle x\), \(\displaystyle y\) számpárokat, és írja a standard output első és egyetlen sorába a medián értékét a végállapotban.

Példa bemenet (a / jelentése újsor karakter): Példa kimenet:
7 4 / 5 5 / 2 4 / 4 6 / 3 5 1

A példában a lépések után a dobozok kavicsainak száma sorrendben: 0, 0, 1, 1, 2, 3, 3, a középső elem az 1.

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.

Beküldendő egy tömörített is5.zip állományban a program forráskódja valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2016. február 10-én LEJÁRT.

Statisztika:

21 dolgozat érkezett.
10 pontot kapott:Alexy Marcell, Bálint Martin, Erdős Márton, Fuisz Gábor, Gáspár Attila, Gergely Patrik, Janzer Orsolya Lili, Kiss Gergely, Kovács 246 Benedek, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Zarándy Álmos.
8 pontot kapott:3 versenyző.
7 pontot kapott:1 versenyző.
6 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2016. januári informatika feladatai