2012-05-05 21:03:39Morris
[UVA][Math] 12024 - Hats
| F - Hats |
Background
John Hatman, the honest cloakroom attendant of the Royal Theatre of London, would like to know the solution to the following problem.
The Problem
When the show finishes, all spectators in the theatre are in a hurry to see the Final of the UEFA Championship. So, they run to the cloakroom to take their hats back.
Some of them take a wrong hat. But, how likely is that everyone take a wrong hat?
The Input
The first line of the input contains an integer, t, indicating the number of test cases. For each test case, one line appears, that contains a number n, 2<=n<=12, representing the number of people and hats.
The Output
For each test case, the output should contain a single line with the number representing the number of favourable cases (i.e., the number of cases where all people take a wrong hat), followed by a bar, "/", and followed by a number representing the total number of possible cases.
Sample Input
3
2
3
4
Sample Output
1/2
2/6
9/24
數學解
N 不排 N 的排法, Fn = Fn-1 * n + (-1)^n;
#include <stdio.h>
int main() {
int N[13] = {0, 0, 1}, P[13] = {1, 1, 2}, n, t;
for(n = 3; n <= 12; n++) {
N[n] = N[n-1]*n + (n%2 == 0 ? 1 : -1);
P[n] = P[n-1]*n;
}
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
printf("%d/%d\n", N[n], P[n]);
}
return 0;
}