Woburn Challenge 1999

The Matrix

Neo is trying to crack the code to break into the computer system of those omnipotent aliens. Whoa!! But even though he has been given the decryption algorithm by Morpheus, he still can't figure it out (remember, this Keanu we're talking about here). So you need to help him break the code.

The system works as follows. The computer will give you a "challenge" - an order set of at most 200 characters, enclosed in round brackets ('(', ')'). To successfully enter the system, you have to answer the challenge by permuting the order of the elements using the given. The correct permutation is obtained by applying one or more permutation matrices to the challenge string as follows: a permutation MATRIX of [1 3 2] means that the 1st character of the challenge string stays 1st, the 3rd character is now 2nd and the 2nd character is now 3rd. So for example, if the challenge set is (a b c) and the permutation matrix is [1 3 2], the counterchallenge is (a c b). Like we said, there may be more than one permutation matrix to apply in which case you apply them from right to left. So if the challenge is (a b c) and the permutation matrices are [3 2 1][1 3 2], the counterchallenge is (b c a). And remember the wise words of Morpheus (ie. us): "everyone will be told what the matrix is."


The input will consist of N, the number of elements in the set and the actual matrices / set on the following line.
Each "matrix" will contain at most 100 numbers, separated by spaces.
There will be at most 100 matrices on each line.
There will be no spaces between any of the brackets ('[', ']', '(', ')') and any characters following. N of -1 denotes end of data.
No line of input will contain more than 200 characters.


For each test case output the correct counterchallenge.
The output must contain one space separating each pair of set elements (there are no spaces between the elements and the brackets!)

Sample Input

[3 2 1][1 3 2](a b c)
[2 1][2 1](a b)

Sample Output

(b c a)
(a b)

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:

Comments (Search)

why is [3 2 1][1 3 2](a b c) = (b c a)

shouldn't it be
(a b c)
[3 2 1] (c b a)
[1 3 2] (c a b)

(c a b)?

Because you do it in reverse order.
You first do [1 3 2] = (a c b),
then [3 2 1] = (b c a)

so what would the counterchallenge be if the challenge was (a b c d) and the permutation was [4 2 1 3] ?

Probably [4 2 1 3] means "the fourth character followed by the second followed by the first followed by the third", giving (d b a c). It isn't clear that it doesn't mean the inverse of this permutation, but it turns out that both will be accepted due to the weakness of the test data.