問題
http://community.topcoder.com/stat?c=problem_statement&pm=11327&rd=14428
様々な種類のうさぎがいる。
そのうちいくつかのうさぎに質問し、自分以外に同じ種類のうさぎが何匹いるか
答えている。
このとき、うさぎの総数について、矛盾しないような最小の数を求める。
解き方
同じ数xを答えたうさぎについて、x＋１匹まで同じ種類二まとめられる。
答えたすべての数xについて、上記から計算できる最小のうさぎの総数を
求める。
コード
class ColorfulRabbits {
public: int getMinimum(vector<int> replies) {
int n=replies.size();
int used[n];
memset(used,0,sizeof(used));
long long ret=0;
FORE(i,0,n)if(!used[i]){
int cnt=0;
FORE(j,0,n)if(replies[i]==replies[j]){
cnt++;
used[j]=1;
}
long long x=replies[i]+1;
ret+=x*((cnt+x-1)/x);
}
return ret;
}
};
public: int getMinimum(vector<int> replies) {
int n=replies.size();
int used[n];
memset(used,0,sizeof(used));
long long ret=0;
FORE(i,0,n)if(!used[i]){
int cnt=0;
FORE(j,0,n)if(replies[i]==replies[j]){
cnt++;
used[j]=1;
}
long long x=replies[i]+1;
ret+=x*((cnt+x-1)/x);
}
return ret;
}
};
Share this
Related Posts
SRM 511 DIV1 Easy - Zoo
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11485&rd=14536
解き方
動物数がN匹であれば、各動物が（０匹，N匹）- SRM 387 DIV1 Easy - FoxesOfTheRoundTable
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8527&rd=11121
解き方
全てのjoker boxの選び方について全探索
- SRM 516 DIV1 Easy - NetworkXOneTimePad
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10846&rd=14541
解き方
すべての暗号前の文字と暗号後の文字の組み合わ
- SRM 553 DIV1 Easy - Suminator
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11354&rd=15175
解き方
プログラムをスタックで実行し、０，１，２で出