AGC005 C - Tree Restoring

問題ページ
C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder

解法

まず、max(a[i]) = Xの距離のグラフをつくることを考える。このグラフをつくるのに
* Xが偶数のとき
距離がX/2の頂点が1個、X/2+1～Xまでの頂点が2個ずつ必要
* Xが奇数のとき
距離がceil(X/2)+1～Xの頂点が2個ずつ必要
となる。このグラフに頂点を付け加えていくことを考えると
* Xが偶数のとき
距離がX/2+1～Xまでの頂点は付け加えられる
* Xが奇数のとき
距離がceil(X/2)+1～Xの頂点は付け加えられる となる。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const int INF = (1LL<<30);
#else
const ll INF = (1LL<<60);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[105], cnt[105];
signed main(void)
{
  int n;
  cin >> n;
  int ma = 0;
  REP(i, n) {
    int a;
    cin >> a;
    cnt[a]++;
    chmax(ma, a);
  }

  if(ma%2==0) {
    for(int i=ma; i>=0; --i) {
      if(i > ma/2) {
        if(cnt[i] < 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else if(i == ma/2) {
        if(cnt[i] != 1) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else {
        if(cnt[i]) {
          cout << "Impossible" << endl;
          return 0;
        }
      }
    }
  } else {
    for(int i=ma; i>=0; --i) {
      if(i > ma/2+1) {
        if(cnt[i] < 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else if(i == ma/2+1) {
        if(cnt[i] != 2) {
          cout << "Impossible" << endl;
          return 0;
        }
      } else {
        if(cnt[i]) {
          cout << "Impossible" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Possible" << endl;

  return 0;
}