TITLE: Problem D. GoroSort

#contents

#br

* 問題 [#xaa5d224]

五郎は4つの腕を持っている。
五郎はとても強い。
あなたは五郎に関わらない方がいいだろう。

五郎は N 個の異なった整数をソートしなければならない。
五郎はアルゴリズムが得意じゃない、五郎の強みは力だ。

五郎は、2つの手を使いいくつかの要素を押さえつけ、残り2つの手でテーブルを叩きつけることを計画している。
これを実行すると、押さえつけていない要素が空中へ飛び、ランダムにシャッフルされた後、要素が配列の空いている場所へ戻る。

五郎は可能な限り、すばやく配列をソートしたいと思っている。
五郎は賢いため、どれを押さえつければ早くソートされるかを知っている。
あなたには、五郎が何回テーブルを叩きつければいいかを求めて欲しい。

五郎は配列を保持するため、2つの手に無数の指を持っている。

五郎はテーブルを叩きつける前に、押さえつける要素を複数選ぶことができる。
五郎は、以前の結果に応じて、異なる選択をすることができる。
テーブルを叩きつけた際に、押さえつけていない要素がランダムに入れ替わる。

テーブルを叩きつけた際のシャッフルは、完全なランダムと考えてよい。
* 入力 [#he551952]

#pre{{
T
N
X1 X2 ... XN
...
}}

複数のデータセットが入力として与えられる。
入力の1行目はデータセットの個数 T である。
2行目から T 個のデータセットが続く。

一つのデータセットは2行からなる。
データセットの1行目は、ソートすべき整数の個数 N である。
2行目には、実際にソートすべき整数 X が N 個並んでいる。

* 出力 [#jb36832a]

#pre{{
Case #x: y
...
}}

データセットごとに1行出力せよ。
出力する値は、データセットの番号 y (1 から始まる) 及び、ソートされるまでに五郎が机を叩く回数 x の期待値である。
x は 10^(-6) 以下の誤差を含んでよい。
* 制限 [#q7096517]

1 ≦ T ≦ 100

** データセット (小) [#m397523b]

1 ≦ N ≦ 10

** データセット (大) [#s1dbf84d]

1 ≦ N ≦ 1000;
* サンプル入出力 [#cffc9efb]

** 入力 [#t689348a]

#pre{{
3
2
2 1
3
1 3 2
4
2 1 4 3
}}

** 出力 [#wbd73c11]

#pre{{
Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000
}}

** 解説 [#s90a60e2]
サンプル入出力のデータセット #3 について解説する。
この場合は、左の二つの要素を固定し、右の二つの要素 4, 3 をシャッフルする。
順番が違う2つの要素が正しい順番になる期待値は 2 である。

その後、五郎は右の2つの要素を固定し、左の二つの要素 2, 1 をシャッフルする。
この期待値は 2 である。

よって、答えは 4 になる。

* ヒント [#ta8323a0]

#region
重複していない N 個の要素を順番に並べる期待値は N です。
#endregion
* 提出・原文 [#rb563936]
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3


* 回答例 [#ude52e49]
|作成者|ソースコード|
|&areaedit(){pine};|&attachref(./GCJ_2011QRD_GoroSort.cpp);|
[&addline(file,above){入力欄を追加};]

#br

-----

#pcomment