using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { int itemCount = int.Parse(Reader.ReadLine()); this.Items = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray(); int total = Items.Sum(a => a); if(total %2 !=0) { Console.WriteLine("impossible"); return; } string ans = "impossible"; if (getAns(0, total / 2)) { ans = "possible"; } Console.WriteLine(ans); } private Dictionary> dic = new Dictionary>(); private bool getAns(int idx, int remain) { if(idx >= this.Items.Length) { return remain == 0; } if(remain == 0) { return true; } if(remain < 0) { return false; } if(!dic.ContainsKey(idx)) { dic.Add(idx, new Dictionary()); } if(dic[idx].ContainsKey(remain)) { return dic[idx][remain]; } bool ret = getAns(idx + 1, remain - Items[idx]); if(!ret) { ret = getAns(idx + 1, remain); } dic[idx][remain] = ret; return ret; } private int[] Items; public class Reader { private static StringReader sr; public static bool IsDebug = false; public static string ReadLine() { if (IsDebug) { if (sr == null) { sr = new StringReader(InputText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } private static string InputText = @" 3 1 2 3 "; } public static void Main(string[] args) { #if DEBUG Reader.IsDebug = true; #endif Program prg = new Program(); prg.Proc(); } }