CodeSky 代码之空

随手记录自己的学习过程

SMU 算法题:BobWu的胜率统计

2014-05-31 22:10分类: C评论: 0

大家玩了很久,由于之前就有过大家玩游戏的记录,大家开始查看各自的胜率,游戏的结果对于每个人就两种,要么就赢,要么就输,今天大家玩了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])这样求出的就是分母了,没想到辗转相除法能这么用,不由得给那一次的上机题点赞了,数学不好的人科普福音啊。

估计效率也不咋的,凑合着用……

PS:科普链接:http://androidguy.blog.51cto.com/974126/1219145

评论 (0)