Reversort Engineering

Reversort는 서로 다른 정수로 이루어진 리스트를 오름차순으로 정렬하는 알고리즘이다. 이 알고리즘은 "Reverse" 연산을 사용한다. 이 연산을 한 번 적용하면 리스트의 어떤 연속한 부분의 순서가 뒤집힌다.

알고리즘의 의사 코드는 다음과 같다.

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

i-1번의 반복이 끝난 뒤 리스트의 1, 2, ..., i-1번째 위치에는 L에서 가장 작은 i-1개의 원소가 오름차순으로 들어 있다. i번째 반복에서는 i번째 위치부터 i번째로 작은 원소가 현재 있는 위치까지의 부분 리스트를 뒤집는다. 그러면 i번째로 작은 원소가 i번째 위치에 오게 된다.

예를 들어 원소가 4개인 리스트라면 알고리즘은 3번의 반복을 수행한다. L=[4,2,1,3]을 처리하는 과정은 다음과 같다.

1. i=1, j=3 ⟶ L=[1,2,4,3]
2. i=2, j=2 ⟶ L=[1,2,4,3]
3. i=3, j=4 ⟶ L=[1,2,3,4]

우리 구조에서 이 알고리즘을 실행할 때 가장 큰 비용이 드는 부분은 Reverse 연산이다. 따라서 각 반복의 비용은 Reverse에 넘겨지는 부분 리스트의 길이, 즉 j-i+1로 정의한다. 알고리즘 전체의 비용은 각 반복의 비용을 모두 더한 값이다.

위 예에서 각 반복의 비용은 차례로 3, 1, 2이고 총합은 6이다.

크기 N과 비용 C가 주어진다. Reversort를 적용했을 때 비용이 정확히 C가 되는, 1과 N 사이의 서로 다른 정수 N개로 이루어진 리스트를 찾거나, 그러한 리스트가 없음을 밝혀라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 원하는 리스트의 크기 N과 목표 비용 C가 정수로 주어진다.

각 테스트 케이스에 대해, Reversort를 적용한 비용이 정확히 C가 되는 크기 N의 리스트가 없으면 Case #x: IMPOSSIBLE 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. 그러한 리스트가 있으면 Case #x: y1 y2 ... yN 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, 각 yi는 1과 N 사이의 서로 다른 정수이며 그러한 리스트 중 하나의 i번째 원소이다.

• 1 ≤ T ≤ 100.
• 1 ≤ C ≤ 1000.

예제 1은 위 문제 지문에서 설명한 경우이다.

예제 2에서 알고리즘은 제시된 출력에 대해 한 번만 반복한다. 그 반복에서 Reverse는 크기 1인 부분 리스트에 적용되므로 비용은 1이다.

예제 3에서 첫 번째 반복은 리스트 전체를 뒤집고 비용은 7이다. 그 뒤 리스트는 이미 정렬되어 있지만 반복이 5번 더 남아 있고, 각각 비용 1을 더한다. 또 다른 유효한 출력으로 7 5 4 3 2 1 6이 있다. 이 출력에서는 첫 번째 반복의 비용이 6, 마지막 반복의 비용이 2이고 나머지는 모두 1이다.

예제 4에서 Reversort는 반드시 6번 반복하며 각 반복의 비용은 1 이상이므로, 총 비용이 요구된 값만큼 작아질 수는 없다.