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])
这样求出的就是分母了,没想到辗转相除法能这么用,不由得给那一次的上机题点赞了,数学不好的人科普福音啊。
估计效率也不咋的,凑合着用……
植入部分
如果您觉得文章不错,可以通过赞助支持我。
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。