2015
04-14

# 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.

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

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

#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;
}


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~), niwenxianq@qq.com
* 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;
}