Problem S. 84. (November 2013)
S. 84. Pete and his brother play the following game. Pete asks his brother to think of a sequence of distinct positive integers with N terms. His brother then encodes this sequence as follows. The number at the position is replaced by a number c, where c is the length of the longest strictly increasing subsequence of the original sequence with the last term of the subsequence being the
element of the original sequence (but elements of the subsequence are not necessarily consecutive elements of the original sequence). For example, if the original sequence is 3 1 2 4 8 20 10, then its encoded version is 1 1 2 3 4 5 5. The brother tells Pete the encoded sequence. Pete's task is to find a sequence such that its encoded version would be identical to the one he got from his brother. Your program should help Pete's task.
Your program should read the value of N () from the first line of the standard input, then the terms of the encoded sequence (integers separated by a space) from the next line. The first and only line of the standard output should contain a sequence (consisting of N positive integers) whose encoded version is the input sequence. Since there are multiple solutions in general, it is enough to display one. Numbers in the input are bounded by 10000000 from above, and this bound should also hold for numbers in the output. The output should consist of distinct integers.
In the example, a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet'') is displayed.
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 N
5 or N500.
The source code (s84.pas, s84.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s84.txt, s84.pdf, ...) - also describing which developer environment to use for compiling the source - should be submitted in a compressed file s84.zip.
(10 pont)
Deadline expired on December 10, 2013.
Sorry, the solution is available only in Hungarian. Google translation
Mintamegoldásnak Molnár-Sáska Zoltán megoldását tesszük közzé. s84.zip
Statistics:
25 students sent a solution. 10 points: Alexy Marcell, Farkas Domonkos, Fonyó Viktória, Jákli Aida Karolina, Juhász 326 Dániel, Kiss 666 Péter, Makk László, Manz Günter, Molnár-Sáska Zoltán, Németh 123 Balázs, Somogyvári Kristóf, Uzonyi 000 Ákos, Weisz Ambrus, Zalavári Márton. 9 points: Halmosi Bence, Kókai Kristóf, Kovács-Deák Máté, Olexó Gergely. 8 points: 2 students. 4 points: 2 students. 1 point: 2 students. 0 point: 1 student.
Problems in Information Technology of KöMaL, November 2013