// 修正(ret[p.first] -> ret[p.first]++). #include using namespace std; // 天秤で計測可能な重さの合計を更新する. // @param m: 重さの合計のリスト. // @param w: 分銅. // @return ret: 更新した重さの合計のリスト. map updateBalance(map m, int w){ map ret; ret[w]++; for(auto &p : m) ret[p.first]++, ret[p.first + w]++; // for(auto &p : ret) cout << "updateBalance(ret): " << p.first << " "; // cout << endl; return ret; } int main() { // 1. 入力情報取得. int N; cin >> N; int W[N]; cin >> W[0]; int total = W[0]; for(int i = 1; i < N; i++){ cin >> W[i]; total += W[i]; } // 2. 重さ合計が奇数なら, 存在しないので, 終了. if(total % 2 != 0){ cout << "impossible" << endl; return 0; } // 3. 天秤で計測可能な重さの合計を更新していく. int half = total / 2; map m; m[W[0]]++; for(int i = 1; i < N; i++){ map lm = updateBalance(m, W[i]); swap(m, lm); } // cout << "half=" << half << endl; // for(auto &p : m) cout << p.first << " "; // cout << endl; // 4. 出力 ~ 後処理. // ex. // 30 // 1 2 3 5 7 7 8 9 9 9 11 11 11 12 13 15 16 16 17 18 5 55 23 1 24 3 4 7 8 20 // total=350, half=175 で, // left: 1 1 3 3 4 5 5 7 7 7 8 8 9 9 9 11 11 11 12 13 15 16 // right: 2, 16, 17, 18, 20, 23, 24, 55 // -> possible と思われる. string ans = (m[half] > 0) ? "possible" : "impossible"; cout << ans << endl; return 0; }