标签 算法 下的文章

SMU算法题 Weijie环

在欢送会上，大家决定玩一个游戏，这个游戏叫做Weijie 环，所有的N 个人站成一圈，由一个人随意说一个数字A，从他顺时针下一个人开始顺时针数，第A个人出圈（下次就不数出圈的人），然后从第A 个人顺时针后面1 个人开始顺时针数A+1，第A+1 个人出圈，依次数A+2，A+3……，最后留在圈内的人获胜。
现在轮到BobWu 说数字，他报出了一个数字A，现在BobWu 想知道自己是第几个出列的。

详情：http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=2

好像以前看过类似的题，不过没做出来，当时也没准备做……结果发现就其本身而言不用数组也可以。

- 阅读剩余部分 -

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

SMU 算法题：Weijie 的客人名单

题目：

去年的主人公Weijie 要离开海事大学了，于是大家决定帮他举行欢送宴会。
BobWu 很想知道究竟有多少人参加了Weijie 的欢送宴会，于是他弄来了客人名单。名单有N 行，但是其中有很多重复的名字，比方BOBWU > 和BobWu 其实指的都是同一个人，但是名单上的名字却区分大小写重复出现了。
BobWu 想知道去除重复的名字以后究竟有哪些客人。

具体可见：http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=1

写了半天……结果还是问了师匠：

- 阅读剩余部分 -

  1. 1
  2. 2