Problem I/S. 5. (January 2016)

I/S. 5. We are given \(\displaystyle N\) initially empty boxes (\(\displaystyle 1 \le N \le 1\;000\;000\), \(\displaystyle N\) is an odd integer). We repeat the following procedure: in a single step we put some stones into certain neighboring boxes (each neighboring box will have one new stone). We will perform \(\displaystyle K\) steps (\(\displaystyle 1\le K \le 25\;000\)), and each step is described by two numbers \(\displaystyle x\), \(\displaystyle y\) (\(\displaystyle x\le y\)), meaning that in the actual step we put a stone into each box between the \(\displaystyle x^\mathrm{th}\) and \(\displaystyle y^\mathrm{th}\) boxes. We are then interested in the median of the number of stones in the \(\displaystyle N\) boxes. The median of a sequence having an odd number of terms is the center element in the sorted version of the sequence.

Your program should read the values of \(\displaystyle N\) and \(\displaystyle K\) from the first line of the standard input, then the pairs \(\displaystyle x\), \(\displaystyle y\) from the next \(\displaystyle K\) lines. The first and only line of the standard output should contain the median at the final state.

In this example the number of stones in the boxes at the final state in increasing order is 0, 0, 1, 1, 2, 3, 3, hence the median is 1.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file is5.zip.

(10 pont)

Deadline expired on February 10, 2016.

Statistics:

21 students sent a solution.
10 points:	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 points:	3 students.
7 points:	1 student.
6 points:	1 student.
4 points:	1 student.
2 points:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, January 2016