Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

Problem I/S. 2. (October 2015)

I/S. 2. In this task you should determine the $\displaystyle k^\mathrm{th}$ permutation among all, lexicographically ordered permutations of length $\displaystyle n$ ($\displaystyle 1\le n\le 14$ és $\displaystyle 1\le k\le n!$).

A permutation of length $\displaystyle n$ can be thought of as a sequence of numbers $\displaystyle 1,2, \ldots, n$ in some given order. A permutation $\displaystyle p_1$ is said to precede another permutation $\displaystyle p_2$ in the lexicographic order, if the first different digit (read from the left) of $\displaystyle p_1$ is smaller than that of $\displaystyle p_2$. For example, the permutation $\displaystyle 2314$ for $\displaystyle n=4$ precedes the permutation $\displaystyle 2341$, so we write $\displaystyle 2314< 2341$.

Your program should read the values of $\displaystyle n$ and $\displaystyle k$ from the first line of the standard input, then write the corresponding permutation to the first and only line of the standard output.

 Sample input: Sample output: 4 2 1 2 4 3

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 without the .exe or any other auxiliary files generated by the compiler but with a short documentation$\displaystyle -$also describing which developer environment to use for compiling the source$\displaystyle -$should be submitted in a compressed file is2.zip.

(10 pont)

Deadline expired on November 10, 2015.

Statistics:

 29 students sent a solution. 10 points: Bálint Martin, Borbényi Márton, Csenger Géza, Erdős Márton, Fuisz Gábor, Gáspár Attila, Gergely Patrik, Hornák Bence, Horváth Miklós Zsigmond, Janzer Orsolya Lili, Kovács 246 Benedek, Kovács Marcell Dorián , Mernyei Péter, Molnár-Sáska Zoltán, Nagy Ábel, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Radnai Bálint, Szakály Marcell, Zarándy Álmos. 9 points: Cseh Viktor. 8 points: 7 students.

Problems in Information Technology of KöMaL, October 2015