using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int MaxSumOfAToJ = 8700; //10個の数の和の上限
static int[] HeihouSuuArr; //MaxSumOfAToJ以下の平方数の配列
static int[] HeihouDiffArr; //平方数同士の差の配列
static void Main()
{
Console.WriteLine("10個の数の和を、{0}以下として検証します", MaxSumOfAToJ);
var sw = System.Diagnostics.Stopwatch.StartNew();
IntiSyori(); //初期処理
for (int I = 10 * (10 + 1) / 2; I <= MaxSumOfAToJ; I++) {
bool IsFoundAnswer;
ExecKensyou(I, out IsFoundAnswer);
if (IsFoundAnswer) break;
}
Console.WriteLine();
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//初期処理
static void IntiSyori()
{
var HeihouSuuList = new List<int>();
var HeihouDiffList = new List<int>();
for (int I = 1; I * I <= MaxSumOfAToJ; I++) {
//平方数は、1+2+3+4+5+6+7+8+9以上
if (I * I < 9 * (9 + 1) / 2) continue;
HeihouSuuList.Add(I * I);
for (int J = 0; J <= HeihouSuuList.Count - 1 - 1; J++) {
HeihouDiffList.Add(I * I - HeihouSuuList[J]);
}
}
HeihouSuuArr = HeihouSuuList.ToArray();
HeihouDiffArr = HeihouDiffList.Distinct().OrderBy(X => X).ToArray();
}
struct JyoutaiDef
{
internal int CurrVal;
internal List<int> ValList;
}
//SumOfAToJを引数として、解を検証
static void ExecKensyou(int pSumOfAToJ, out bool pIsFoundAnswer)
{
pIsFoundAnswer = false;
Console.WriteLine("10個の数の和を、{0}として検証中", pSumOfAToJ);
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
for (int I = 1; I <= pSumOfAToJ; I++) {
//等差数列の和 = (初項+末項)*項数/2
int wkSum = (I + I + 9) * 10 / 2;
if (pSumOfAToJ < wkSum) break;
if (Array.BinarySearch(HeihouSuuArr, pSumOfAToJ - I) < 0) continue;
WillPush.CurrVal = I;
WillPush.ValList = new List<int>() { I };
stk.Push(WillPush);
}
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
int Cnt = Popped.ValList.Count;
int CurrSum = Popped.ValList.Sum();
if (Cnt == 10) {
Console.WriteLine("解候補を発見");
PrintAnswer(Popped.ValList.ToArray());
pIsFoundAnswer = true;
continue;
}
for (int I = 0; I <= HeihouDiffArr.GetUpperBound(0); I++) {
int NextVal = Popped.CurrVal + HeihouDiffArr[I];
if (Cnt == 9) {
if (CurrSum + NextVal < pSumOfAToJ) continue;
if (CurrSum + NextVal > pSumOfAToJ) break;
}
else {
//残りの数個を加算した場合に、和が上限を超えたら枝切り
int RestCnt = 10 - Cnt;
if (CurrSum + NextVal * RestCnt > pSumOfAToJ) break;
}
if (Array.BinarySearch(HeihouSuuArr, pSumOfAToJ - NextVal) < 0) continue;
WillPush.CurrVal = NextVal;
WillPush.ValList = new List<int>(Popped.ValList) { NextVal };
stk.Push(WillPush);
}
}
}
//解を出力
static void PrintAnswer(int[] pAToJ)
{
int wkSum = pAToJ.Sum();
//平方根を求める
Func<int, int> GetHeihouKon = (pVal) =>
{
return (int)Math.Sqrt(pVal);
};
int A = pAToJ[0];
int B = pAToJ[1];
int C = pAToJ[2];
int D = pAToJ[3];
int E = pAToJ[4];
int F = pAToJ[5];
int G = pAToJ[6];
int H = pAToJ[7];
int I = pAToJ[8];
int J = pAToJ[9];
string wkStr = "A={0},B={1},C={2},D={3},E={4},F={5},G={6},H={7},I={8},J={9}";
Console.WriteLine(wkStr, A, B, C, D, E, F, G, H, I, J);
Console.WriteLine("A+B+C+D+E+F+G+H+I = {0} ({1}の2乗)", wkSum - J, GetHeihouKon(wkSum - J));
Console.WriteLine("A+B+C+D+E+F+G+H +J = {0} ({1}の2乗)", wkSum - I, GetHeihouKon(wkSum - I));
Console.WriteLine("A+B+C+D+E+F+G +I+J = {0} ({1}の2乗)", wkSum - H, GetHeihouKon(wkSum - H));
Console.WriteLine("A+B+C+D+E+F +H+I+J = {0} ({1}の2乗)", wkSum - G, GetHeihouKon(wkSum - G));
Console.WriteLine("A+B+C+D+E +G+H+I+J = {0} ({1}の2乗)", wkSum - F, GetHeihouKon(wkSum - F));
Console.WriteLine("A+B+C+D +F+G+H+I+J = {0} ({1}の2乗)", wkSum - E, GetHeihouKon(wkSum - E));
Console.WriteLine("A+B+C +E+F+G+H+I+J = {0} ({1}の2乗)", wkSum - D, GetHeihouKon(wkSum - D));
Console.WriteLine("A+B +D+E+F+G+H+I+J = {0} ({1}の2乗)", wkSum - C, GetHeihouKon(wkSum - C));
Console.WriteLine("A +C+D+E+F+G+H+I+J = {0} ({1}の2乗)", wkSum - B, GetHeihouKon(wkSum - B));
Console.WriteLine(" B+C+D+E+F+G+H+I+J = {0} ({1}の2乗)", wkSum - A, GetHeihouKon(wkSum - A));
Console.WriteLine();
Console.WriteLine("A+B+C+D+E+F+G+H+I+J={0}", wkSum);
}
}