AGC005-C Tree Restoring (700)

木の性質

木は直径の部分にいっぱいくっつけたものと思っとけばいい

解説を見た

1. #include<iostream>
2. #include<algorithm>
3. #define lol(i,n) for(int i=0;i<n;i++)
4. using namespace std;
5. int n,a[110],cnt[110];
6. int main(){
7. cin>>n;
8. lol(i,n)cnt[i]=0;
9. int maxi=0;
10. lol(i,n){
11. cin>>a[i];
12. cnt[a[i]]++;
13. maxi=max(maxi,a[i]);
14. }
15. bool ok=true;
16. for(int i=0;i<(maxi+1)/2;i++)if(cnt[i]>0)ok=false;
17. if(maxi%2==0&&cnt[(maxi+1)/2]!=1)ok=false;
18. if(maxi%2==1&&cnt[(maxi+1)/2]!=2)ok=false;
19. for(int i=(maxi+1)/2+1;i<=maxi;i++)if(cnt[i]<2)ok=false;
20. cout<<(ok?"Possible":"Impossible")<<endl;;
21. return 0;
22. }

700点チャレンジ2問目