Problem S. 85. (December 2013)
S. 85. We are given a sequence of N positive integers ai, with N
100000 and 1ai1000000000. 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 1C1000000000.
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 January 10, 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:
Statistics:
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.
Problems in Information Technology of KöMaL, December 2013