PKU 1804. Brainman.

뇌인간(?)

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 3041	Accepted: 1737

설명

배경
Raymond Babbitt은 동생 Charlie 를 미치도록 몰아댔다. 최근 Raymond는 246개의 이쑤시게를 바닥에 흩뿌려놓고는 힐끗힐끗 쳐다보기만 했다. 그리고 심지어는 포커 카드를 세기까지 했다. 찰리는 같은 방식으로 머리를 쓰게 해서 엿먹이고 싶어 한다.

문제
찰리가 생각한 것은 이러하다. N개의 숫자가 늘어진 수열이 있다고 하자. 목표는 이 수열이 최종적으로 정렬되게 하는 것인데, 한번에 이웃한 두개의 숫자밖에 바꿀 수 없다. 예를 들면 :
Start with: 2 8 0 3 
swap (2 8) 8 2 0 3 
swap (2 0) 8 0 2 3 
swap (2 3) 8 0 3 2 
swap (8 0) 0 8 3 2 
swap (8 3) 0 3 8 2 
swap (8 2) 0 3 2 8 
swap (3 2) 0 2 3 8 
swap (3 8) 0 2 8 3 
swap (8 3) 0 2 3 8
이리하여 (2 8 0 3) 는 9회만에 처리가 된다. 하지만 더 빠른 방법도 있다.
Start with: 2 8 0 3 
swap (8 0) 2 0 8 3 
swap (2 0) 0 2 8 3 
swap (8 3) 0 2 3 8
질문의 요지는 이러하다. "정렬까지 최소 몇번 움직여야 하는가?". 풀 수 있을까?

입력

첫 줄은 시나리오의 갯수.
각 시나리오에 대해서 첫 수는 수열에 존재하는 숫자의 갯수 N이고, 이후 N개의 수열 내에 존재할 숫자들의 초기 순서대로 숫자가 하나씩 들어온다. 각 숫자는 -1000000 부터 1000000 사이의 수를 갖게 된다.

출력

첫번째 시나리오부터 시작해서 각 시나리오당 "Scenario #i:"를 출력한 후, 그 다음 줄에 최소 정렬 횟수를 출력한다. 각 시나리오간에는 한 줄의 빈 줄이 존재한다.

입력 예시

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

출력 예시

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

출처

TUD Programming Contest 2003, Darmstadt, Germany

역자주 - 원문은 상당히 개소리로 난잡합니다.
그냥 편하게 읽으시라고 핵심부분 빼고 맘대로 의역했습니다. -_-;;