1부터 n까지 숫자가 적혀있는 n 개의 카드가 위에서 아래로 오름차순으로 정렬되어있다. 그리고, 1이상 자연수 여러개가 담긴 배열 k_list 가 주어졌을 때, 머쓱이는 k_list에서 순서대로 하나씩 k를 꺼내서 다음과 같은 방법으로 카드를 섞는다.
- 아래쪽부터 위쪽으로 k개의 카드를 잡는다.
- 잡은 카드를 나머지 카드들의 위로 올린다.
- 2번에서 잡은 카드의 아래부터 절반을 잡아서 2번을 반복한다. a. 2번에서 잡은 카드의 개수가 짝수라면 (잡은 카드의 개수) / 2 만큼 절반을 잡는다. b. 2번에서 잡은 카드의 개수가 홀수라면 (잡은 카드의 개수 + 1) / 2 만큼 절반을 잡는다.
- 3번에서 잡은 카드의 절반의 개수가 1이면 카드들의 맨위로 올리고 섞기를 종료한다.
k_list에 있는 모든 k에 대해 위와 같은 방법으로 카드를 섞은 후 최종 카드의 상태를 반환하자.
n은 2 이상 1000 이하의 수로 주어진다. k는 1 이상 n 미만의 수로 주어진다. k_list의 길이는 1이상 100 이하이다.
| n | k_list | return |
|---|---|---|
| 10 | [5,1,2,5,3] | [9, 10, 5, 2, 1, 7, 8, 6, 4, 3] |
예제 #1
k에 따른 카드 섞기의 결과는 다음과 같다.
| k | cards |
|---|---|
| 처음 | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
| 5 | [10, 9, 8, 6, 7, 1, 2, 3, 4, 5] |
| 1 | [5, 10, 9, 8, 6, 7, 1, 2, 3, 4] |
| 2 | [4, 3, 5, 10, 9, 8, 6, 7, 1, 2] |
| 5 | [2, 1, 7, 8, 6, 4, 3, 5, 10, 9] |
| 3 | [9, 10, 5, 2, 1, 7, 8, 6, 4, 3] |
아래 그림은 첫 번째 k가 5일 때 섞이는 과정을 나타낸다.
모든 k에 대하여 섞은 후의 결과는 [9, 10, 5, 2, 1, 7, 8, 6, 4, 3]이다.