KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Sample input (here / means new line):Sample output:
7 4 / 5 5 / 2 4 / 4 6 / 3 51

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 10 February 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley