Informatica Online Judge

  번호표 교환 [1410 / 0582]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 52   Total Tried : 144


The Champion of this Problem (C++) : gs17067 - 0ms / 196byte
My Best Submission (C++) : N/A

[JOI15/16예선]

Background

이번 시간에는 melongist선생님께서 학생들과 재미있는 게임을 한다.

교실에는 n명의 학생들이 한 줄로 서 있다.

각 학생들은 번호표를 하나씩 가지고 있다.

i번째 학생의 번호표에 적힌 수는 a_i 이다.

그리고 m개의 카드가 있다. 이 카드는 1부터 m까지의 값을 가진다.

각 카드는 반드시 1부터 사용하며, k ( 2 <= k <= m )번 카드는 k-1번 카드를 쓴 다음에 쓴다.

게임의 규칙은 다음과 같다.

선생님이 1번 학생에게 i번 카드를 준다. ( 1 <= i <= m )

카드를 받은 j번 학생은 j+1번 학생에게 카드를 넘긴다.

단, a_j % i의 값이 a_(j+1)%i 의 값보다 크면 두 학생의 번호표를 서로 교환한다.

마지막 학생이 카드를 받으면 그 카드는 버린다.

이 과정은 마지막 m번 카드까지 버리면 끝난다.


정확한 과정은 입력예를 보면 이해하기 쉽다.

이 과정을 모두 마친 후의 각 학생들이 가진 번호표를 순서대로 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 학생의 수와 카드의 수를 나타내는 정수 n, m이 공백으로 구분되어 입력된다.

두 번째 줄부터 n줄에 걸쳐서 각 학생이 가지는 번호표의 값이 주어진다.

[입력값의 정의역]
1 <= n, m <= 100
1 <= a_i <= 1,000

Output

게임이 종료된 후에 각 학생이 가지는 번호표의 값을 공백으로 구분하여 출력한다.

IO Example

입력
6 4
3 2 8 3 1 5

출력
2 3 1 8 5 3

* 설명 :

1번 카드를 사용한 후의 학생들의 번호표 : 3 2 8 3 1 5
2번 카드를 사용한 후의 학생들의 번호표 : 2 8 3 3 1 5
3번 카드를 사용한 후의 학생들의 번호표 : 2 3 3 1 8 5
4번 카드를 사용한 후의 학생들의 번호표 : 2 3 1 8 5 3

따라서 2 3 1 8 5 3 이 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]