SRM 500 DIV1 Easy - MafiaGame

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11342&rd=14429

解き方


投票数が一番多い人が最後に残る候補となる。
よってそれがX人だとすると、最後に1人残るのであれば
確率は1/Xとなる。

最後に一人残るかどうかの判定は、NをX人で割った余りを更新していき
割り切れるのであれば全員消滅してしまうので答えは0になる。
最後に1人残れば上記の確率を返す。

コード


class MafiaGame {

public: double probabilityToLose(int N, vector<int> decisions) {
map<int,int> m;
FORE(i,0,decisions.size())m[decisions[i]]++;

int mx=0,cnt=0;
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
mx=max(mx,it->second);
}
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
if(mx==it->second)cnt++;
}

if(mx==1)return 0.0;
double ret=1.0/cnt;

while(cnt>1){
if(N%cnt==0)return 0.0;
cnt=N%cnt;
}

return ret;
}

};

Share this

Related Posts

Previous
Next Post »