TPERML - Permutation generator

Dla każdego indeksu (numeru permutacji w porządku leksykograficznym zaczynając od 0) n-elementowej permutacji wydrukuj m kolejnych permutacji (w oddzielnych liniach) w porządku leksykograficznym zaczynając od permutacji wskazywanej przez indeks. Odpowiedzi dla kolejnych testów należy oddzielić od siebie pustymi liniami. Przyjmiemy, że następną permutacją po ostatniej jest pierwsza.

Wejście

t [liczba zestawów testowych <= 1000]
n index m [2 <= n <= 100 - liczba elementów w permutacji, 0 <= index < n! - indeks pierwszej permutacji, 1 <= m <= 100 - liczba permutacji do wydrukowania]

Wyjście

p1 p2 ... p(n-1) pn [permutacje]
p1 p2 ... pn p(n-1)

p1 p2 ... p(n-1) pn [permutacje]
p1 p2 ... pn p(n-1)


Przykład

Wejście:
12
2 1 1
3 3 3
4 16 3
4 5 9
2 1 1
2 1 1
3 5 1
5 91 7
2 1 1
5 100 7
3 5 1
2 1 1

Wyjście:
2 1

2 3 1
3 1 2
3 2 1

3 4 1 2
3 4 2 1
4 1 2 3

1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2

2 1

2 1

3 2 1

4 5 1 3 2
4 5 2 1 3
4 5 2 3 1
4 5 3 1 2
4 5 3 2 1
5 1 2 3 4
5 1 2 4 3

2 1

5 1 4 2 3
5 1 4 3 2
5 2 1 3 4
5 2 1 4 3
5 2 3 1 4
5 2 3 4 1
5 2 4 1 3

3 2 1

2 1

Added by:Piotr Piotrowski
Date:2004-11-25
Time limit:4.505s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET

hide comments
2020-01-04 04:46:22
Pythonists beware, xrange in Py2 cannot handle arguments larger than 32bit integer. Use range, itertools.slice or submit in Py3.
2016-08-03 19:24:05 Madhukar Reddy
Is it possible for two different test cases be in same line separated by space?

Last edit: 2016-08-03 19:24:24
2016-03-18 18:36:19
Getting runtime error (SIGXFSZ)
Any suggestions?
2015-06-30 08:46:30 Purav Shah
@Piotr Piotrowski: Could u check my attempts, I'm getting WA and I think they are because of the output format

EDIT: Got AC....
1) Use string to input index
2) Use array and not string for modification of index

Last edit: 2015-08-29 08:27:42
2012-08-26 05:10:16 srikardurgi
what is SGARBT error ...
my program works fine for the given test case.. what should be done to get rid of this error

Last edit: 2012-08-26 05:10:45
2012-02-01 09:49:28 Devil D
@Santiago: value of factorials can go into big ints..
2011-07-10 04:48:32 Santiago Palacio
@govardhan: i dont think any biginteger is necesary, as biggest number to handle is 1000 (in t) and 100 in permutations.

EDIT: Any tricky test case? i'm getting all examples ok, managing well the empty lines, but i keep getting WA. As it seems, m can be 0. How do i manage that?

Last edit: 2011-08-22 05:25:29
2011-03-31 17:09:54 Govardhan Reddy M
should i have to use only bigInt to read index ?? how to do in C ?? customized bigIndex ?? please help
2009-06-30 19:37:09 .:: Pratik ::.
Huge output, try to use fast output.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.