using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication1
{
    /// <summary>
    /// http://digg.com/playable_web_games/I_challenge_you_to_win_this_game?t=11535140#c11575842
    /// http://www.games.jaxey.com/45.html
    /// Just go to the end and change the 3, 4, 5, 6 into any other list you want in case you want
    /// to get a solution for a different setup. Remember the number of rows can also be changed,
    /// for instance you can try 3, 4, 5, 6, 7.
    /// </summary>
    class Program
    {
        static private int RowCount = 4;
        private class State
        {
            private int[] marbles;
            public State() { marbles = new int[RowCount]; }
            public State(State s) {
                marbles = new int[RowCount];
                Array.Copy(s.marbles, marbles, RowCount);
            }
            public int this[int index] {
                get {return marbles[index];}
                set { marbles[index] = value; }
            }
            public override bool Equals(object obj)
            {
                if (obj is State) {
                    State s = (State)obj;
                    if (s.marbles.Length != marbles.Length) return false;
                    for (int i = 0; i < RowCount; ++i)
                        if (marbles[i] != s.marbles[i]) return false;
                    return true;
                }
                else return false;
            }
            public override int GetHashCode() {
                return marbles[0] + marbles[RowCount - 1];
            }
            public override string ToString() {
                string s = "";
                for (int i = 0; i < marbles.Length; ++i) {
                    if (i > 0) s += ",";
                    s += marbles[i];
                }
                return s;
            }
            public void sort() {
                Array.Sort(marbles);
            }
        }
        private Dictionary<State, string> memory;
        private string WiningMove(State curstate) {
            State state = new State(curstate);
            state.sort();
            if (memory.ContainsKey(state)) return memory[state];
            if ((state[RowCount - 1] == 1 || state[RowCount - 1] == 0) && state[RowCount - 2] == 0) return null;
            string result = null;
            for (int i = 0; result==null && i < RowCount; ++i) {
                int nmarbles = state[i];
                for (int j = 0; result==null && j < nmarbles; ++j) {
                    state[i] = j;
                    result = WiningMove(state);
                    if (result == null) result=state.ToString();
                    else result = null;
                }
                state[i] = nmarbles;
            }
            memory.Add(new State(state), result);
            return result;
        }
        public Program(int[] ubounds) {
            memory = new Dictionary<State, string>();
            RowCount = ubounds.Length;

            for (int i = 0; i < ubounds.Length; ++i) ubounds[i]++;
            State s = new State();
            int nProduct = 1;
            for (int j = 0; j < ubounds.Length; ++j)
                nProduct *= ubounds[j];
            for (int i = 1; i < nProduct; ++i) {
                int n = i;
                bool invalid=false;
                for (int j = ubounds.Length - 1; j >= 0; --j) {
                    s[j] = n % ubounds[j]; n /= ubounds[j];
                    if (j<ubounds.Length-1 && s[j] > s[j + 1]) invalid = true;
                }
                if (invalid) continue;
                Debug.Assert(n == 0);
                Console.Write(s + ": ");
                string winner = WiningMove(s);
                if (winner == null) Console.WriteLine("Lost.");
                else Console.WriteLine(winner);
            }
        }
        static void Main(string[] args) {
            new Program(new int[] { 3, 4, 5, 6 });
            Console.Read();
        }
    }
}