CARD - Cardsharper
Zenek is a well known (at least in Byteotia) card-sharper. He spent most of his best years practicing one card shuffle with his deck of n cards, which for simplicity we will call 1, 2, ..., n. Unfortunately, it turns out that knowing this one card shuffle a is not enough to earn a good living. To become rich and famous Zenek needs to know k shuffles c1, ..., ck. As he doesn't have enough time to learn all of them, he decided to learn only one shuffle b so that using both a and b he will be able to perform as many of ci as it is possible.
Each shuffle is described by n numbers t1, t2, ..., tn. Such description means that after performing shuffle, card that was originally at position i will be at position ti.
Task
Find shuffle b maximizing number of shuffles that can be performed.
Input
First line contains n (2 ≤ n ≤ 52). Second line contains n numbers a1, a2, ..., an describing shuffle that Zenek already knows. Third line contains k (2 ≤ k ≤ 6). i-th of the next k lines contains description of ci.
Output
First line contains description of the shuffle b that Zenek should learn. i-th of the next k lines contains:
-
-1
when it is not possible to perform ci using only a and b - m, r1, r2, ..., rm (0 ≤ m ≤ 500000, 0 ≤ ri ≤ 106) meaning that applying a r1 times, then b r2 times, then a r3 times and so on is the same as applying shuffle ci once.
Examples
Input
5 2 3 4 5 1 3 1 3 2 4 5 1 2 3 4 5 5 4 3 2 1
Output
2 1 3 4 5 3 4 1 1 0 9 1 1 3 1 4 1 1 1 1
Input
5 1 2 3 4 5 3 1 3 2 4 5 5 4 3 2 1 1 2 5 4 3
Output
1 3 2 4 5 2 0 1 -1 -1
hide comments
korsic:
2020-05-14 18:01:09
the problem is so good. there even exists one conceptually simple solution, a solution with few explicit steps. i loved it! |
|
asinop:
2016-12-05 07:32:50
great problem. Last edit: 2016-12-06 04:40:40 |
|
gawry:
2015-09-15 14:24:14
Mark Gritter: any b such that every c_i can be produced as specified in the statement will be accepted. |
|
taleb.alali:
2015-04-04 22:29:02
Output
|
|
Mark Gritter:
2014-12-08 13:25:01
I think I overstated the case, only the conjugates aba^-1 a^2ba^-2 etc. are alternate solutions. |
|
Mark Gritter:
2014-12-08 13:25:01
If 'b' is a solution, then isn't 'aba^-1' also a solution? Or 'ab'? Or 'a^2ba^3'? Is there some additional restriction on the number of shuffles performed (the word length) or would all these possibilities be accepted as valid answers? |
|
gawry:
2014-12-08 13:25:01
He can learn any shuffle, doesn't have to be one from the input.
|
|
Darth Vadar:
2014-12-08 13:25:01
shoudn't he learn one of the shuffles provided in the i/p or any type of shuffle he can learn???? |
Added by: | gawry |
Date: | 2007-09-20 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Fajne Zawody Informatyczne |