首页 > ACM题库 > HDU-杭电 > HDU 3959-Board Game Dice-数学相关-[解题报告]HOJ
2015
04-14

HDU 3959-Board Game Dice-数学相关-[解题报告]HOJ

Board Game Dice

问题描述 :

hh is a Board Game hobbyist, he often plays Board Game such as Catan, Carcassonne, The Werewolves, A song of ice and fire with friends.
To play the games, we need some dices, and these dices are very unusual. Maybe with eight or twelve sides.
Tower Defence

hh plays with N friends today(including himself). They’ll choose one person to be the judge. But the problem is: there is only a M-sided dice. How to pick a judge with the dice, so that everyone has equal probability of being chosen (the probability should always be 1/N)?
hh has an idea here:
1)Get x
Decide rolling the dice x times. x is the smallest integer to make Mx larger than or equal to N.

2)Players choose sequences
Each player chooses a sequence with x elements (1~M).
For example, a 6-sides dice and x equal to 3, hh will gets sequence [5 4 6]. Players’ sequences should be different from each other.(such as [6 4 5] is different from [5 4 6])

3)Pick the judge
Roll the dice for x times, we can get a result sequence, if someone has the same sequence as the result, he will be the judge; otherwise, repeat 1)-3), until the judge is chosen.

It’s a bigger project, hh wants know the expected number of times we will need to throw dice to determine the judge.

输入:

The first line is a number T(1<=T<=100), which represents the number of cases. The next T blocks following are the cases.
Each case contains two integer N , M(2<=N<=109, 2<=M<=20)

输出:

The first line is a number T(1<=T<=100), which represents the number of cases. The next T blocks following are the cases.
Each case contains two integer N , M(2<=N<=109, 2<=M<=20)

样例输入:

2
3 2
9 3

样例输出:

Case 1: 8/3
Case 2: 2/1

 题意有点绕,想了很久 , 还是求教金思密达才明白了题意 , 才出的这个题。

题目就是要找一个比N大的M^x,得到M^x*x/N的最简分数 , 根据样例,分子是1时不用处理,直接除去gcd就好

没估出范围,还是改成long long交的 , 后来试一下 int WA了。

#include <cstdio>

typedef long long typen;

typen gcd (typen a , typen b){
    return b?gcd(b,a%b):a;
}

typen n,m;
int main ()
{
    int cas;
    scanf("%d",&cas);
    for (int I=1 ; I<=cas ; ++I)
    {
        scanf("%I64d%I64d",&n,&m);
        typen x=1;
        typen tmp=m;
        for ( ; tmp<n ; ++x,tmp*=m);
        //printf("x=%d\n",x);
        typen p,q;
        p=tmp*x;q=n;
        typen d=gcd (p,q);
        printf("Case %d: %I64d/%I64d\n",I,p/d,q/d);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/jxy859/article/details/6699247


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }