SMU 算法题：BobWu的胜率统计
大家玩了很久，由于之前就有过大家玩游戏的记录，大家开始查看各自的胜率，游戏的结果对于每个人就两种，要么就赢，要么就输，今天大家玩了D 局，大家总共玩了G 局，但是当BobWu 查看胜率记录的时候，发现自己的今天的胜率恰好是一个整数PD，自己的总胜率也恰巧是一个整数PG！他开始怀疑是不是因为大家玩游戏输掉会被惩罚喝酒于是计算错了。可是由于大家都喝酒了，谁都记不得今天玩了几局（D），也记不得总共玩了几局（G），但是可以确定今天一定不可能玩超过了N 局（D≤N）现在BobWu 想知道这样的胜率究竟是有可能，还是一定计算错了。
题目详情：http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=3
1#include <stdio.h>
2
3int divide(int big, int small)
4{
5 int r;
6
7 r = big % small;
8
9 while (r != 0)
10 {
11 big = small;
12 small = r;
13 r = big % small;
14 }
15
16 return small;
17}
18
19int main(void)
20{
21 unsigned int n[100], pd[100], pg[100], t, possible[100], big = 100, temp;
22 int i;
23
24 scanf("%u", &t);
25 for (i = 0; i < t; i++)
26 {
27 scanf("%u", &n[i]);
28 scanf("%u", &pd[i]);
29 scanf("%u", &pg[i]);
30
31 if (100 / divide(100, pd[i]) > n[i])
32 possible[i] = 0;
33
34 if( pg[i] > 100 || pg[i] == 100 && pd[i] != 100 || pg[i] == 0&& pd[i] != 0)
35 possible[i] = 0;
36 else
37 possible[i] = 1;
38 }
39
40 for (i = 0; i < t; i++)
41 {
42 switch (possible[i])
43 {
44 case 1:
45 printf("Case #%d: Possible\n", i + 1);
46 break;
47 case 0:
48 printf("Case #%d: Broken\n", i + 1);
49 break;
50 }
51 }
52
53 return 0;
54}
55
在我按了半天计算器之后，终于发现，要计算的是分母，而且要最简形式，问题就转换了，可是关键是怎么求……于是我尝试了各种方法，按了好多遍计算器最终发现求公约数就可以了OTZ100 / divide(100, pd[i])这样求出的就是分母了，没想到辗转相除法能这么用，不由得给那一次的上机题点赞了，数学不好的人科普福音啊。
估计效率也不咋的，凑合着用……
评论 (0)