using System;
using System.Collections.Generic;
class Program
{
struct NumInfo
{
internal string NumStr;
internal int CorrectCnt;
}
static void Main()
{
var Q1NumInfoList = new List<NumInfo>();
var Q2NumInfoList = new List<NumInfo>();
Action<List<NumInfo>, string, int> AddAct = (pList, pNumStr, pCorrectCnt) =>
pList.Add(new NumInfo() { NumStr = pNumStr, CorrectCnt = pCorrectCnt });
AddAct(Q1NumInfoList, "90342", 2);
AddAct(Q1NumInfoList, "70794", 0);
AddAct(Q1NumInfoList, "39458", 2);
AddAct(Q1NumInfoList, "34109", 1);
AddAct(Q1NumInfoList, "51545", 2);
AddAct(Q1NumInfoList, "12531", 1);
AddAct(Q2NumInfoList, "5616185650518293", 2);
AddAct(Q2NumInfoList, "3847439647293047", 1);
AddAct(Q2NumInfoList, "5855462940810587", 3);
AddAct(Q2NumInfoList, "9742855507068353", 3);
AddAct(Q2NumInfoList, "4296849643607543", 3);
AddAct(Q2NumInfoList, "3174248439465858", 1);
AddAct(Q2NumInfoList, "4513559094146117", 2);
AddAct(Q2NumInfoList, "7890971548908067", 3);
AddAct(Q2NumInfoList, "8157356344118483", 1);
AddAct(Q2NumInfoList, "2615250744386899", 2);
AddAct(Q2NumInfoList, "8690095851526254", 3);
AddAct(Q2NumInfoList, "6375711915077050", 1);
AddAct(Q2NumInfoList, "6913859173121360", 1);
AddAct(Q2NumInfoList, "6442889055042768", 2);
AddAct(Q2NumInfoList, "2321386104303845", 0);
AddAct(Q2NumInfoList, "2326509471271448", 2);
AddAct(Q2NumInfoList, "5251583379644322", 2);
AddAct(Q2NumInfoList, "1748270476758276", 3);
AddAct(Q2NumInfoList, "4895722652190306", 1);
AddAct(Q2NumInfoList, "3041631117224635", 3);
AddAct(Q2NumInfoList, "1841236454324589", 3);
AddAct(Q2NumInfoList, "2659862637316867", 2);
Solve(Q1NumInfoList.ToArray());
Solve(Q2NumInfoList.ToArray());
}
struct JyoutaiDef
{
internal int CurrInd;
internal string CurrStr;
internal int[] CorrectCntArr;
}
static void Solve(NumInfo[] pNumInfoArr)
{
int StrLen = pNumInfoArr[0].NumStr.Length;
int UB = pNumInfoArr.GetUpperBound(0);
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrInd = 0;
WillPush.CurrStr = "";
WillPush.CorrectCntArr = new int[UB + 1];
Stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
int EdakiriCnt = 0;
int PopCnt = 0;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (++PopCnt % 100000 == 0) {
Console.WriteLine("{0}回目のPop内容={1}", PopCnt, Popped.CurrStr);
}
//クリア判定
if (Popped.CurrStr.Length == StrLen) {
bool IsClear = true;
for (int I = 0; I <= UB; I++) {
if (Popped.CorrectCntArr[I] != pNumInfoArr[I].CorrectCnt) {
IsClear = false;
break;
}
}
if (IsClear) {
Console.WriteLine("解は={0}", Popped.CurrStr);
}
continue;
}
WillPush.CurrInd = Popped.CurrInd + 1;
for (char I = '0'; I <= '9'; I++) {
WillPush.CurrStr = Popped.CurrStr + I.ToString();
WillPush.CorrectCntArr = (int[])Popped.CorrectCntArr.Clone();
bool IsOK = true;
for (int J = 0; J <= UB; J++) {
if (I == pNumInfoArr[J].NumStr[Popped.CurrInd]) {
WillPush.CorrectCntArr[J]++;
if (WillPush.CorrectCntArr[J] > pNumInfoArr[J].CorrectCnt) {
IsOK = false;
break;
}
}
}
if (IsOK) {
string Hash = GetHash(WillPush);
if (VisitedSet.Add(Hash)) {
Stk.Push(WillPush);
}
//else {
// ++EdakiriCnt;
// if (EdakiriCnt % 10000 == 0)
// Console.WriteLine("{0}回目の枝切り。状態数={1}", EdakiriCnt, VisitedSet.Count);
//}
}
}
}
}
//訪問ノードのハッシュ値を返す
static string GetHash(JyoutaiDef pJyoutai)
{
var sb = new System.Text.StringBuilder();
sb.AppendFormat("{0},", pJyoutai.CurrInd);
Array.ForEach(pJyoutai.CorrectCntArr, X => sb.Append(X));
return sb.ToString();
}
}