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

#include <stdio.h>

int divide(int big, int small)
{
    int r;

    r = big % small;

    while (r != 0)
    {
        big = small;
        small = r;
        r = big % small;
    }

     return small;
}

int main(void)
{
    unsigned int n[100], pd[100], pg[100], t, possible[100], big = 100, temp;
    int i;

    scanf("%u", &t);
    for (i = 0; i < t; i++)
    {
        scanf("%u", &n[i]);
        scanf("%u", &pd[i]);
        scanf("%u", &pg[i]);

        if (100 / divide(100, pd[i]) > n[i])
            possible[i] = 0;

        if( pg[i] > 100 || pg[i] == 100 && pd[i] != 100 || pg[i] == 0&& pd[i] != 0)
            possible[i] = 0;
        else
            possible[i] = 1;
    }

    for (i = 0; i < t; i++)
    {
        switch (possible[i])
        {
            case 1:
                printf("Case #%d: Possible\n", i + 1);
                break;
            case 0:
                printf("Case #%d: Broken\n", i + 1);
                break;
        }
    }

    return 0;
}

在我按了半天计算器之后,终于发现,要计算的是分母,而且要最简形式,问题就转换了,可是关键是怎么求……于是我尝试了各种方法,按了好多遍计算器最终发现求公约数就可以了OTZ100 / divide(100, pd[i])这样求出的就是分母了,没想到辗转相除法能这么用,不由得给那一次的上机题点赞了,数学不好的人科普福音啊。

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

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

植入部分

如果您觉得文章不错,可以通过赞助支持我。

如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。

标签: 源码, 代码段, 题目, 算法

添加新评论