神、上帝以及老天爷
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
HDU 2006’10 ACM contest的颁奖晚会隆重开始了! 为了活跃气氛, 组织者举行了一个别开生面、奖品丰厚的抽奖活动, 这个活动的具体要求是这样的：
首先, 所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中; 然后, 待所有字条加入完毕, 每人从箱中取一个字条; 最后, 如果取得的字条上写的就是自己的名字, 那么“恭喜你, 中奖了! ”
大家可以想象一下当时的气氛之热烈, 毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀! 不过, 正如所有试图设计的喜剧往往以悲剧结尾, 这次抽奖活动最后竟然没有一个人中奖!
我的神、上帝以及老天爷呀, 怎么会这样呢?
不过, 先不要激动, 现在问题来了, 你能计算一下发生这种情况的概率吗?
不会算? 难道你也想以悲剧结尾?!
Input
输入数据的第一行是一个整数 C, 表示测试实例的个数, 然后是 C 行数据, 每行包含一个整数 n(1 < n <= 20), 表示参加抽奖的人数。
Output
对于每个测试实例, 请输出发生这种情况的百分比, 每个实例的输出占一行, 结果保留两位小数(四舍五入), 具体格式请参照 sample output。
Sample Input
1
2Sample Output
50.00%Source
Analyze
下面我们讨论a[n], 我们采用递推的思想, 有两种情况:
- 已知抽奖人数为
n-1时所有人都不中奖的情况为a[n-1], 此时将这n-1个人中的某个人与第n个人交换字条, 这时候得到(n-1) * a[n-1]种n个人都不中奖的情况; - 已知抽奖人数为
n-1时只有一个人中奖的情况为b[n-1], 此时将这个中奖的人与第n个人交换字条, 这时候得到b[n-1]种n个人都不中奖的情况。
因此当抽奖人数为n时有 a[n] = (n-1) * a[n-1] + b[n-1]成立
这时候讨论 b[n] 为抽奖人数为 n 时只有一个人中奖的情况:
-
第
n个人中奖, 前n-1个人都没有中奖则有a[n-1]种情况; -
前
n-1个人中有一个人中奖, 而第n个人不中奖, 从前n-1个人中选取某一个人 (记为x) 与持有字条x的人交换字条, 并将x原有的字条给第n个人, 而第n个人的字条给原持有字条x的人, 此时有(n - 1) * a[n-1]种情况。
Code
#include <bits/stdc++.h>
#define fei(a, b) for(int i = a; i <= b; i++)
#define fej(a, b) for(int j = a; j <= b; j++)
#define fni(a, b) for(int i = a; i < b; i++)
#define fnj(a, b) for(int j = a; j < b; j++)
using namespace std;
const int maxn = 20 + 5;
long long a[maxn];
long long b[maxn];
long long c[maxn];
int main()
{
// freopen("in.txt", "r", stdin);
int x;
cin >> x;
a[2] = 1;
b[2] = 0;
fei(3, 20)
{
a[i] = a[i - 1] * (i - 1) + b[i - 1];
b[i] = i * a[i - 1];
}
c[0] = 1;
fei(1, 20)
c[i] = c[i - 1] * i;
while(x--)
{
int n;
cin >> n;
double ans = 1.0 * a[n] / c[n] * 100;
printf("%.2lf", ans);
cout << "%" << endl;
}
return 0;
}