#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() /* No.4 おもりと天秤 dp 解 dp[i][j]:= i 番目のおもりと使ったときの 合計のおもり j dp[0][0] := true; dp[i+1][j] := dp[i][j], dp[i+1][j+w[i]] := dp[i][j] sum(W) % 2 == 0 かつ dp[N][sum(W)/2] ? possible : impossible 計算量 O(N*sum(W)) */ using namespace std; typedef long long ll; typedef pair P; const int MAX_N = 105; const int MAX_W = 105*105; bool dp[MAX_N][MAX_W]; int main() { memset (dp, false, sizeof (dp ) ); ios_base::sync_with_stdio(0); int N; cin >> N; vector W(N, 0 ); rep (i, N ) cin >> W[i]; int sumW = accumulate (ALL (W ), 0 ); dp[0][0] = true; for (int i = 0; i < N; i++ ){ for (int j = 0; j < MAX_W; j++ ){ if (dp[i][j] ){ dp[i+1][j] |= true; // i 番目のおもりを使わない dp[i+1][j+W[i]] |= true; // i 番目のおもりを使う } // end if } // end for } // end for bool res = ((sumW % 2 == 0 ) && dp[N][sumW/2] ); cout << (res ? "possible" : "impossible" ) << endl; return 0; }