//Yukicoder No.4 //重りと天秤 //#include "stdafx.h" #include #include #include #include //list #include //tree #include //連想配列 #include //hash #include //hash #include #include #include #include using namespace std; typedef unsigned long long ULL; typedef signed long long SLL; typedef unsigned int UINT; int memo[2][100]; int N; int W[100]; int possible = 0; int _target_weight = 0; // // 半分の重さになるおもりの組み合わせがあるかを調べる // // n:おもりのインデックス // total_weight:載せた合計の重さ // flag :載せるとき1 載せないとき0 int func(int n, int total_weight, int flag) { //cout << "n=" << n << ", total_weight = " << total_weight << endl; if (possible) return total_weight; if (n >= N) return total_weight; if (_target_weight < total_weight) { return total_weight; } if (_target_weight == total_weight) { possible = 1; return total_weight; } if (memo[flag][n]) return memo[flag][n]; memo[1][n] = func(n + 1, total_weight + W[n],1); //先に n番目を載せた場合を調べる(探索枝を短くするため) memo[0][n] = func(n + 1, total_weight,0); //後から n番目を載せなかった場合を調べる return total_weight; } //降順 int compare(const int * a, const int *b) { if (*a < *b) return (1); else if (*a > *b) return (-1); return (0); } int main() { int total = 0; cin >> N; for (int i=0;i> W[i]; total += W[i]; } if (total % 2) { //そもそも2分割できない合計だったらすぐさまimpossibleを返す cout << "impossible" << endl; return 0; } // 半分に割る _target_weight = total >> 1; //降順のソート qsort(W, N, sizeof(int), (int(*)(const void*, const void*))compare); //半分の重さになるかを深さ(再帰)探索。重たいものから載せる(探索枝を短くするため) func(0,0,1); if (possible == 1) { cout << "possible" << endl; } else { cout << "impossible" << endl; } //getchar(); return 0; }