# -*- coding: utf-8 -*- # 動的計画法(メモ化探索),深さ優先探索: depth first searchの活用 def equal_balance(dp, N, W): weight_sum = sum(W) if weight_sum % 2 == 1: return 'impossible' else: weight_sum /= 2 recurrence_formula(dp, N, W) # if dfs(0, int(weight_sum), dp, N, W): if dp[0][int(weight_sum)]: return 'possible' else: return 'impossible' """ i番目以降の錘を使って合計jの重量にできればTrueを返す(メモには可否を表すbool値を記す) メモ化再帰による実装 この他にも,dp[i][j]にi番目以降の錘を加えた総重量jが目的の総重量であるか否かを記録する方法もある """ def dfs(i, j, dp, N, W): #すでに調べたものは再利用する if dp[i][j] != None: return dp[i][j] is_possible = False if i == N: #錘が存在しない場合は不可能 is_possible = False elif j == 0: #総重量が0場合はTrueを返す(どこかで当初の総重量を達成できたことを意味するため) is_possible = True elif j < W[i]: #i番目の錘が総重量以上の場合は,その錘は使えない #if j == 0: # is_possible = True #else: is_possible = dfs(i+1, j, dp, N, W) else: #i番目の錘を使える場合は,使うときと使わない時の場合を両方考慮する is_possible = (dfs(i+1, j, dp, N, W) or dfs(i+1, j-W[i], dp, N, W)) dp[i][j] = is_possible return is_possible """ 漸化式による実装 2次元配列dpには,i番目以降の錘を使って合計jの重量にできればTrueを記録 """ def recurrence_formula(dp, N, W): for j in range(10001): dp[N][j] = False for i in range(N-1, -1, -1): for j in range(0, 10001): if j == W[i]: dp[i][j] = True elif j < W[i]: dp[i][j] = dp[i+1][j] else: dp[i][j] = (dp[i+1][j] or dp[i+1][j-W[i]]) N = int(input()) W = list(map(int, input().split())) dp = [[None for a in range(10001)] for b in range(N+1)] print(equal_balance(dp, N, W))