| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 290 | 95 | 87 | 52.727% |
태준이는 친구들과 카드 게임을 즐기기 위해 카드 셔플 기계를 구입했다. 모든 게임에서 이기고 싶었던 태준이는 기계의 구조를 분석하여 셔플 결과를 예측하려고 한다.
셔플 기계에는 총 $M$가지의 셔플 기술이 내장되어 있다. $i$번째 셔플 기술은 1ドル$부터 $N$까지 각 수가 정확히 한 번씩 등장하는 길이 $N$의 수열 $S_i$로 표현된다. $i$번째 셔플 기술을 1ドル$번 실행하면, 위에서 $j$번째에 있는 카드는 위에서 $S_{ij}$번째에 위치하게 된다.
셔플 기계를 작동시키면 $K$번의 셔플을 정해진 순서대로 실행한 후 종료된다. 한 번의 셔플은 $X_i$와 $Y_i$ 두 개의 정수로 표현되며, 이는 $X_i$번 셔플 기술을 $Y_i$번 실행한다는 뜻이다.
처음에 카드는 위에서부터 1ドル$번부터 $N$번까지 순서대로 정렬되어 있다. 셔플 기계를 작동시킨 후 카드들이 어떻게 배열되는지 찾아보자.
첫 번째 줄에 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다.
다음 $M$개의 줄 중 $i$번째 줄에는 $i$번째 셔플 기술을 나타내는 $S_{i1}, S_{i2}, \cdots , S_{iN}$이 차례대로 공백으로 구분되어 주어진다.
다음 $K$개의 줄 중 $i$번째 줄에는 $i$번 셔플에서 실행할 셔플 기술의 번호 $X_i$와 해당 기술을 실행할 횟수 $Y_i$가 공백으로 구분되어 주어진다.
셔플 기계를 작동시킨 후 카드의 최종 순서를 위에서부터 순서대로 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $N = 2$ |
| 2 | 23 | $N \leq 100,ドル $M \leq 100,ドル $K \leq 100,ドル $Y_i \leq 10^6$ (1ドル \leq i \leq K$) |
| 3 | 66 | 추가 제약 조건 없음. |
6 2 3 6 5 4 3 2 1 2 4 6 1 3 5 1 3 2 1 1 2
3 6 2 5 1 4
처음에 카드는 [1, 2, 3, 4, 5, 6] 순서대로 배열되어 있다.
처음에 1ドル$번 셔플 기술을 3ドル$번 실행하면 [6, 5, 4, 3, 2, 1]이 된다.
이후 2ドル$번 셔플 기술을 1ドル$번 실행하면 [3, 6, 2, 5, 1, 4]가 된다.
마지막으로 1ドル$번 셔플 기술을 2ドル$번 실행한 이후 결과는 [3, 6, 2, 5, 1, 4]가 된다.
3 2 3 2 3 1 3 1 2 1 2024 2 7 1 28
2 3 1