KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


Problem S. 85. (December 2013)

S. 85. We are given a sequence of N positive integers ai, with N\le100000 and 1\leai\le1000000000. We are looking for significant subsequences of this sequence. A subsequence is said to be significant, if

- it consists of some consecutive elements of the original sequence, and

- its central element is not less than a prescribed number C with 1\leC\le1000000000.

To get the central element of a subsequence, first sort the subsequence into non-decreasing order, then take

- either its middle element when the subsequence length is odd,

- or the not smaller element of the two middle elements when the subsequence length is even.

For example, the central element of the sequence {9,2,1,6} is 6, while the central element of the sequence {4,9,5} is 5.

Since a given sequence has in general a large number of significant subsequences, we are only interested in the number of these significant subsequences.

Your program should read the values of N and C from the first line of the standard input, then the actual elements of the sequence from the next line. Your program should write the number of significant subsequences in the first and only line of the standard output.

In the example, a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet'') are displayed. As an explanation, notice that the following subsequences are significant: {10}, {6}, {10,5}, {5,6}, {6,2}, {10,5,6} and {10,5,6,2}.

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

Partial points can be obtained if your program yields a solution for 200 or 2000.

The source code (s85.pas, s85.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s85.txt, s85.pdf, ...) - also describing which developer environment to use for compiling the source --should be submitted in a compressed file s85.zip.

(10 pont)

Deadline expired on 10 January 2014.

Sorry, the solution is available only in Hungarian. Google translation

Mintamegoldásnak Jákli Aida Karolina megoldását tesszük közzé. S85.zip

Illetve megjegyzem, hogy érdemes utánanézni az úgynevezett intervallumfának, vagy segment tree-nek. Közzéteszem Weisz Ambrus megoldását, illetve egy oktató anyagot a témáról. main.cpp Az anyag:



20 students sent a solution.
10 points:Jákli Aida Karolina, Kiss 666 Péter, Makk László, Németh 123 Balázs, Somogyvári Kristóf, Weisz Ambrus.
9 points:Zalavári Márton.
8 points:1 student.
7 points:1 student.
6 points:4 students.
4 points:1 student.
2 points:2 students.
1 point:4 students.

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