2015
04-16

# A Card Game

There are N cards on the table, whose front side is writen one integer number from 1 to M. We call one card "a type k card" if its number is k. The quantity of type i cards is a_i.
Let’s play a game with these cards. We divide these cards into M piles by random with the only constrains that the quantity of cards in i-th (indexed from 1) pile must exactly be a_i. The possbility of each card appears in i-th pile is directly proportional to the size of this pile. That is to say, if the size of a pile is A, the possibility for each card appears in this pile is A/N assuming that N is the amount of all cards. We choose pile 1 to start the game. Assuming the we now play this game at pile k, we randomly choose a card from pile k with the same possibility for all cards in it, remember the number written on this card and throw it away. If the number on the chosen card is j, we continue this game at pile j on next round. The game terminates when we are going to get a card from an empty pile.

Now the question is, when the game ends, what is the possibility that all piles are empty?

There is only one input file. The first line is the number of test cases T. T cases follow, each of which contains two lines. The first line is an integer M (1 <= M <= 100), the number of type of cards (and the number of piles, they are exactly the same). The second line contains M positive integers not greater than 1000, the i-th number of which is a_i.

There is only one input file. The first line is the number of test cases T. T cases follow, each of which contains two lines. The first line is an integer M (1 <= M <= 100), the number of type of cards (and the number of piles, they are exactly the same). The second line contains M positive integers not greater than 1000, the i-th number of which is a_i.

2
1
5
2
1 2

Case 1: 1.000000
Case 2: 0.333333

2、在序列中，由于游戏是从第一堆开始的，所以第一个数虽然没有前驱，但是他是放在第 1 堆的。所以如果 1 不为最后一个数，那么第一堆中必然有a[1]+1个数了，不行。
3、序列中的最后一个数 记 i ，如果不为 1 ，那么值 i 就只有a[i]-1个后继了。
4、结合2、3，易知只有最后一个数为 1 ，堆容量a[i]才会都符合。才能根据此序列构造一种符合的分堆及取牌（题目原意是随机取的）情况，即一一对应。

/*
Pro: 0

Sol:

date:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
int t,m;
double f,sum,tmp;
int main(){
scanf("%d",&t);
for(int ca = 1; ca <= t; ca ++){
scanf("%d",&m);
sum = 0;
m --; scanf("%lf",&f); sum += f;
while(m --) scanf("%lf",&tmp), sum += tmp;//这里啊。。。。
printf("Case %d: %.6f\n",ca,f / sum);
}
return 0;
}