//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 N; int W[100]; int possible = 0; int _target_weight = 0; // // 半分の重さになるおもりの組み合わせがあるかを調べる // // n:おもりのインデックス // total_weight:載せた合計の重さ    void func(int n, int total_weight) { if (possible) return; if (n >= N) return; if (_target_weight < total_weight) return; if (_target_weight == total_weight) { possible = 1; return; } func(n + 1, total_weight + W[n]); //先に n番目を載せた場合を調べる(探索枝を短くするため) func(n + 1, total_weight); //後から n番目を載せなかった場合を調べる return; } //降順 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); if (possible == 1) { cout << "possible" << endl; } else { cout << "impossible" << endl; } //getchar(); return 0; }