Problem 3440 --GoroSort

3440: GoroSort

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table? Goro has an infinite number of fingers on the two hands he uses to hold down the array.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each one will consist of two lines. The first line will give the number N. The second line will list the N elements of the array in their initial order.
1 ≤ T ≤ 100;
The second line of each test case will contain a permutation of the N smallest positive integers.
1 ≤ N ≤ 1000;

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of hit-the-table operations when following the best hold-down strategy. Answers with an absolute or relative error of at most 10-6 will be considered correct.

Sample Input复制

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

Sample Output复制

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

提示

In test case #3, one possible strategy is to hold down the two leftmost elements first. Elements 3 and 4 will be free to move. After a table hit, they will land in the correct order [3, 4] with probability 1/2 and in the wrong order [4, 3] with probability 1/2. Therefore, on average it will take 2 hits to arrange them in the correct order. After that, Goro can hold down elements 3 and 4 and hit the table until 1 and 2 land in the correct order, which will take another 2 hits, on average. The total is then 2 + 2 = 4 hits.

推荐代码 查看3440 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] aoj_judger 613603 2020-10-01 18:07:04
内存最少[$1120 $KB] aoj_judger 613603 2020-10-01 18:07:04
第一AC aoj_judger 613603 2020-10-01 18:07:04
第一挑战 aoj_judger 613603 2020-10-01 18:07:04

赛题来源/所属竞赛 Google Code Jam 2011 资格赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛