1:
2:
3:
4:
5:
6:
7:
8:

8(8) 0(5) 0(3) 
3(8) 5(5) 0(3) 
3(8) 2(5) 3(3) 
6(8) 2(5) 0(3) 
6(8) 0(5) 2(3) 
1(8) 5(5) 2(3) 
1(8) 4(5) 3(3) 
4(8) 4(5) 0(3)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:

using System;
using System.Collections.Generic;

namespace Weintrinker
{
	class MainClass
	{
		private static int encode (int[] curr, int[] max)
		{
			int result = 0;
			for (int i = 0; i < curr.Length - 1; i++) { //no need to add last item, as sum = const
				result *= max [i] + 1;
				result += curr [i];
			}
			return result;
		}

		private static int[] decode (int curr, int[] max, int sum)
		{
			int[] result = new int[max.Length];
			int sum_tmp = 0;
			for (int i = max.Length - 2; i >= 0; i--) {
				result [i] = curr % (max [i] + 1);
				sum_tmp += result [i];
				curr /= (max [i] + 1);
			}
			result [result.Length - 1] = sum - sum_tmp;
			return result;
		}

		private static List<int> getFollowing (int state, int[] max, int sum, List<int[]> index, out bool success)
		{
			List<int> result = new List<int> ();
			success = false;
			int[] curr = decode (state, max, sum);
			for (int source = 0; source < curr.Length; source++) {
				if (curr [source] == 0)
					continue;
				for (int dest = 0; dest < curr.Length; dest++) {
					if (curr [dest] == max [dest] || dest == source)
						continue;
					int fill = Math.Min (curr [source], max [dest] - curr [dest]);
					int[] nextState = (int[])curr.Clone ();
					nextState [source] -= fill;
					nextState [dest] += fill;
					result.Add (encode (nextState, max));
					//test if solution found
					int sumFirst = 0;
					foreach (int i in index[0])
						sumFirst += nextState [i];
					bool allSumsEqual = true;
					for (int i = 1; i < index.Count && allSumsEqual; i++) {
						int sumCurrent = 0;
						foreach (int j in index[i])
							sumCurrent += nextState [j];
						if (sumCurrent != sumFirst)
							allSumsEqual = false;
					}
					if (allSumsEqual) {
						success = true;
						return result; //solution is the last item in the list
					}
				}
			}
			return result;
		}

		private static string Solve (List<int[]> listMax, List<int[]> listCurrent)
		{
			int n = 0;
			int sum = 0;
			foreach (int[] personMax in listMax)
				n += personMax.Length;
			int[] max = new int[n];
			int[] curr = new int[n];
			List<int[]> index = new List<int[]> ();
			int currIndex = 0;
			for (int i = 0; i < listMax.Count; i++) {
				index.Add (new int[listMax [i].Length]);
				for (int j = 0; j < listMax[i].Length; j++) {
					max [currIndex] = listMax [i] [j];
					curr [currIndex] = listCurrent [i] [j];
					sum += curr [currIndex];
					index [i] [j] = currIndex++;
				}
			}
			//states[steps to reach state] < currentState, previousState>
			List<Dictionary<int, int>> states = new List<Dictionary<int, int>> ();
			states.Add (new Dictionary<int, int> ());
			states [0].Add (encode (curr, max), 0);
			bool success = false;
			int[] path;
			for (int moves = 1; states[moves-1].Count > 0; moves++) {
				states.Add (new Dictionary<int, int> ());
				foreach (KeyValuePair<int, int> entry in states[moves - 1]) {
					List<int> followingStates = getFollowing (entry.Key, max, sum, index, out success);
					foreach (int next in followingStates) {
						bool add = true;
						for (int j = 0; j <= moves; j++)
							if (states [j].ContainsKey (next)) {
								add = false;
								continue;
							}
						if (add) 
							states [moves].Add (next, entry.Key);
					}
					if (success) {
						path = new int[moves + 1];
						path [path.Length - 1] = followingStates [followingStates.Count - 1];
						goto solutionFound;
					}
				}
			}
			return "no solution found\n";
			solutionFound:
			for (int i = path.Length - 2; i >= 0; i--)
				path [i] = states [i + 1] [path [i + 1]];
			string solution = "";
			for (int i = 0; i < path.Length; i++) {
				int[] vals = decode (path [i], max, sum);
				for (int j= 0; j < vals.Length; j++)
					solution += vals [j] + "(" + max [j] + ") ";
				solution += "\n";
			}
			return solution;
		}

		public static void Main (string[] args)
		{
			List<int[]> max = new List<int[]> ();
			List<int[]> curr = new List<int[]> ();
			max.Add (new int[] { 8 });
			max.Add (new int[] { 5, 3 });
			curr.Add (new int[] { 8 });
			curr.Add (new int[] { 0, 0 });
			Console.Write (Solve (max, curr));
			max.Clear (); curr.Clear ();
			max.Add (new int[] { 10, 8 });
			max.Add (new int[] { 11, 7 });
			curr.Add (new int[] { 10, 4 });
			curr.Add (new int[] { 4, 6 });
			Console.Write (Solve (max, curr));
		}
	}
}