using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input4"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("3"); WillReturn.Add("1 2 3"); } else if (InputPattern == "Input2") { WillReturn.Add("5"); WillReturn.Add("1 2 3 4 5"); } else if (InputPattern == "Input3") { WillReturn.Add("15"); WillReturn.Add("62 8 90 2 24 62 38 64 76 60 30 76 80 74 72"); } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int CurrP; internal List SelectedIndList; } struct MemoDef { internal int CurrP; internal int CurrSum; } static void Main() { List InputList = GetInputList(); int[] OmoriArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray(); int UB = OmoriArr.GetUpperBound(0); //事前に総合計を求めておく int OmoriSum = OmoriArr.Sum(); //総合計が奇数なら解なし if (OmoriSum % 2 == 1) { Console.WriteLine("impossible"); return; } var MemoList = new List(); var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrP = 0; WillPush.SelectedIndList = new List() { 0 }; stk.Push(WillPush); bool FoundAnswer = false; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); int SelectedSum = DeriveSelectedSum(OmoriArr, Popped.SelectedIndList); //クリア判定 if (SelectedSum == OmoriSum / 2) { Console.WriteLine("解を発見"); Popped.SelectedIndList.ForEach(X => Console.WriteLine(OmoriArr[X])); FoundAnswer = true; break; } if (Popped.CurrP >= OmoriArr.GetUpperBound(0)) continue; for (int I = Popped.CurrP + 1; I <= UB; I++) { //下限値枝切り int wkSum = SelectedSum; for (int J = I; J <= UB; J++) { wkSum += OmoriArr[J]; } if (wkSum < OmoriSum / 2) break; //Push処理 WillPush.CurrP = I; WillPush.SelectedIndList = new List(Popped.SelectedIndList) { I }; //メモ化探索で再訪禁止 int NewOmoriSum = DeriveSelectedSum(OmoriArr, WillPush.SelectedIndList); if (MemoList.Exists(X => X.CurrP == WillPush.CurrP && X.CurrSum == NewOmoriSum)) continue; stk.Push(WillPush); } } Console.WriteLine(FoundAnswer ? "possible" : "impossible"); } //添え字のリストを引数として重りの合計を返す static int DeriveSelectedSum(int[] pOmoriArr, List pSelectedIndArr) { int WillReturn = 0; pSelectedIndArr.ForEach(X => WillReturn += pOmoriArr[X]); return WillReturn; } }