Problem D. GoroSort

問題

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

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

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

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

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

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

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

入力

T
N
X1 X2 ... XN
...

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

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

出力

Case #x: y
...

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

制限

1 ≦ T ≦ 100

データセット (小)

1 ≦ N ≦ 10

データセット (大)

1 ≦ N ≦ 1000;

サンプル入出力

入力

3
2
2 1
3
1 3 2
4
2 1 4 3

出力

Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

解説

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

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

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

ヒント

提出・原文

http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

回答例

作成者	ソースコード
pine[e]	GCJ_2011QRD_GoroSort.cpp

[入力欄を追加]