首页 > ACM题库 > HDU-杭电 > HDU 4061-A Card Game-概率-[解题报告]HOJ
2015
04-16

HDU 4061-A Card Game-概率-[解题报告]HOJ

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

还是YY难求。wa的原因是将逗号写成了分号。。。

答案是第一个数/总的数的和。 http://blog.csdn.net/tclh123/article/details/6849679

其实就是M种牌放到M堆里,M种牌和M堆都是从1~M编号的。输入 M, 然后输入M个数,表示M种牌分别有多少张,同时也表示M堆分别的最大容量是多少。游戏是这样玩的,从第一堆开始由顶向下取(简单起见),取到的牌属于第k种,就接着到第k堆取。当任何一次取不到牌时,游戏结束。求游戏结束时牌恰好被取完的概率。
分析:假设取的牌顺序是一个序列,那么这种序列在末尾为1时是和取牌序列一一对应的,且是符合“游戏结束时牌恰好被取完”的一种情况。
简证:1、在序列中,任一数 i 的后一个数 j 是必然要放在第 i 堆里的。而值为 i 的数有 a[i]个,所以在 i 后面的数也恰好a[i]个,所以a[i]个数被放到第 i 堆,符合题目约束条件。
2、在序列中,由于游戏是从第一堆开始的,所以第一个数虽然没有前驱,但是他是放在第 1 堆的。所以如果 1 不为最后一个数,那么第一堆中必然有a[1]+1个数了,不行。
3、序列中的最后一个数 记 i ,如果不为 1 ,那么值 i 就只有a[i]-1个后继了。
4、结合2、3,易知只有最后一个数为 1 ,堆容量a[i]才会都符合。才能根据此序列构造一种符合的分堆及取牌(题目原意是随机取的)情况,即一一对应。
所以至此,题目转变为N个数的全排列,其中最后一个数为1的概率是多少。先从a[1]个1里取一个1,有a[1]种,然后剩下的N-1个数全排列有(N-1)!种,所以总共符合有a[1]*(N-1)!种。而N个数全排列有N!种。所以概率为a[1]/N。而N = sum(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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/7927733