Permutaciones P90339
Una permutación del conjunto { 1, 2, … , n} es una manera de ordenar esos números. Por ejemplo, [123], [132], [213], [231], [312], y [321] son las 6 posibles permutaciones para n = 3.
Un modo alternativo de describir una permutación es dando sus ciclos. Por ejemplo, la permutación [6351274] se puede escribir (1 6 7 4) (2 3 5). Ésto es, a la posición 1 va el 6, a la posición 6 va el 7, a la posición 7 va el 4, a la posición 4 va el 1 (primer ciclo), a la posición 2 va el 3, a la posición 3 va el 5, y a la posición 5 va el 2 (segundo ciclo). Nótese que hay varias maneras de describir una permutación mediante ciclos. Por ejemplo, la última permutación también se puede escribir como (3 5 2) (6 7 4 1).
Como se puede ver a, una misma permutación se puede aplicar repetidamente. Así, aplicando 2 veces [6351274] se obtiene [7526341] = (7 1) (6 4) (5 3 2).
Después de 3 veces se tiene [4237516] = (4 7 6 1) (2) (3) (5), y después de 4 veces [1364267] = (1) (4) (6) (7) (3 5 2). Es fácil ver que después de 12 veces se obtendría [1234567] = (1) (2) (3) (4) (5) (6) (7).
Hacer un programa que, para cada permutación dada, escriba el resultado de aplicarla un cierto número de veces.
Entrada
La entrada consiste en una secuencia de casos. Cada caso empieza con una línea con n, c, y m (respectivamente, el número de elementos de la permutación, su número de ciclos, y el número de pruebas). Siguen c líneas, una por ciclo. Cada ciclo sigue exactamente el formato de los ejemplos. A continuación vienen m líneas, cada una con k (el número de veces que se tiene que aplicar la permutación). Podeis asumir 1 ≤ n ≤ 10000, 1 ≤ c ≤ n, m ≥ 1, y k ≥ 1.
Salida
Para cada caso de la entrada, hay que escribir la permutación que se obtiene después de aplicar k veces la permutación dada. Escribir una línea en blanco al final de las respuestas para cada caso. Seguir el formato de los ejemplos.
Puntuación
- TestA: 25 Puntos
Algunos juegos de pruebas contendrán exclusivamente casos como los del ejemplo de entrada 1, en los que todas las k son 1.
- TestB: 20 Puntos
Algunos juegos de pruebas contendrán exclusivamente casos como los del ejemplo de entrada 2, en los que k ≤ 100.
- TestC: 55 Puntos
Otros juegos de pruebas contendrán casos de todo tipo, en los que k ≤ 109.
Input
7 2 3 (1 6 7 4) (2 3 5) 1 1 1 4 4 1 (1) (4) (2) (3) 1
Output
6 3 5 1 2 7 4 6 3 5 1 2 7 4 6 3 5 1 2 7 4 1 2 3 4
Input
7 2 8 (1 6 7 4) (2 3 5) 1 2 3 4 12 16 20 24 4 1 3 (2 3 4 1) 1 2 100
Output
6 3 5 1 2 7 4 7 5 2 6 3 4 1 4 2 3 7 5 1 6 1 3 5 4 2 6 7 1 2 3 4 5 6 7 1 3 5 4 2 6 7 1 5 2 4 3 6 7 1 2 3 4 5 6 7 2 3 4 1 3 4 1 2 1 2 3 4
Input
7 2 1 (3 5 2) (6 7 4 1) 1000000000
Output
1 3 5 4 2 6 7
- Author
- Omer Giménez
- Language
- Spanish
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++