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