SRM 511 DIV1 Easy - Zoo

SRM 511 DIV1 Easy - Zoo

13:03

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11485&rd=14536

解き方


動物数がN匹であれば、各動物が（０匹，N匹）〜（N匹、０匹）までの
すべての場合が考えられる。

各場合について、動物が答えている数が一致しているか判定し、
有効であればmin（うさぎの数、猫の数）^2がその場合の総数になる。

コード


class Zoo {

public: long long theCount(vector<int> answers) {
long long ret=0;
int n=answers.size();

map<int,int> m;
FORE(i,0,n)m[answers[i]]++;

for(int l=0;l<=n;l++){
int r=n-l;
int cnt=0,valid=1;
for(int i=0;i<min(l,r);i++){
if(m[i]!=2)valid=0;
cnt+=m[i];
}
for(int i=min(l,r);i<max(l,r);i++){
if(m[i]!=1)valid=0;
cnt+=m[i];
}
if(cnt!=n)valid=0;

if(valid){
ret+=pow(2,min(l,r));
}
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts