import java.util.Stack;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/* Riddle statement: 4 people with a single torch stand at the opening of a tunnel.
 * they would like to get through, but there is a catch. Only two people can go
 * at the same time, the tunnel is too narrow, and they really need to use
 * the torch, because there point black inside the tunnel. Given that each person
 * can go in different speed and when two of them go together their speed is equal
 * to the speed of the slowest of the two. Your goal is make a plan for them such
 * that all of them get to the other side of the tunnel as fast as possible.
 *
 *    PERSON       SPEED
 *  ----------     -----
 *   ME              1
 *   ASSISTENT       2
 *   JANITOR         5
 *   PROFESSOR       10
 *
 * The characters has been inspired by the following YouTube video: https://youtu.be/7yDmGnA8Hw0
 */
public class riddle2
{
    /* Global constants used for encoding the states of the World.
     * For example, the integer encoding the state
     * (ME, ASSISTENT) | (LANTERN, JANITOR, PROFESSOR) is 3 
     * (00011 in binary) alias ME_LEFT | ASSISTENT_LEFT.
     */
    public static final int ME_LEFT        = 1;
    public static final int ASSISTENT_LEFT = 2;
    public static final int JANITOR_LEFT   = 4;
    public static final int PROFESSOR_LEFT = 8;
    public static final int LANTERN_LEFT   = 16;

    /* The maximum number of states in the world. */
    public static final int MAXSTATES = 32;

    /* Bitmask used to get rid of the duration in the state encoding. */
    public static final int STATE_MASK = MAXSTATES - 1;

    /* Keeping the track how we got to each (reachable) state. */
    public static final int[] predecessor = new int[MAXSTATES];

    /* Keeping how long it took to get into the state (situation). */
    public static final int[] duration = new int[MAXSTATES];

    /* Indicates whether we have found the state (situation) in the smallest possible time. */
    public static final boolean[] resolved = new boolean[MAXSTATES];

    /* Compare the states (situations) by the time it took to get into them. */
    public static final Comparator<Integer> stateComparator = new Comparator<Integer>()
    {
        public int compare(Integer one, Integer two)
        {
            return (one >> 5) - (two >> 5);
        }
    };

    /* The only needed sophisticated data structure we would like not to code by ourselves. */
    public static final PriorityQueue<Integer> queue = new PriorityQueue<Integer>(stateComparator);

    public static boolean isValid(int state)
    {
        return !resolved[state];
    }

    public static void tryEnqueueState(Integer nextState, Integer prevState, Integer time)
    {
        if (isValid(nextState) && duration[prevState] + time < duration[nextState])
        {
            /* We can improve on the time we get to the situation. */
            duration[nextState] = duration[prevState] + time;

            /* NOTE that because Java's PriorityQueue does not implement
             * ``decreaseKey`` method, we need to get around it, and this
             * is one way to do it - see the interplay with ``resolved``
             * array and ``stateComparator`` used as comparator in the
             * priority queue.
             */
            queue.add(nextState + (duration[nextState] << 5));
            predecessor[nextState] = prevState;
        }
    }

    public static void expandState(int state)
    {
        if ((state & LANTERN_LEFT) != 0) 
        {
            if ((state & ME_LEFT) != 0)
            {
                tryEnqueueState(state ^ (ME_LEFT | LANTERN_LEFT), state, 1);

                if ((state & ASSISTENT_LEFT) != 0)
                    tryEnqueueState(state ^ (ME_LEFT | ASSISTENT_LEFT | LANTERN_LEFT), state, 2);

                if ((state & JANITOR_LEFT) != 0)
                    tryEnqueueState(state ^ (ME_LEFT | JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) != 0)
                    tryEnqueueState(state ^ (ME_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & ASSISTENT_LEFT) != 0)
            {
                tryEnqueueState(state ^ (ASSISTENT_LEFT | LANTERN_LEFT), state, 2);

                if ((state & JANITOR_LEFT) != 0)
                    tryEnqueueState(state ^ (ASSISTENT_LEFT | JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) != 0)
                    tryEnqueueState(state ^ (ASSISTENT_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & JANITOR_LEFT) != 0)
            {
                tryEnqueueState(state ^ (JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) != 0)
                    tryEnqueueState(state ^ (JANITOR_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & PROFESSOR_LEFT) != 0)
                tryEnqueueState(state ^ (PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
        }
        else
        {
            if ((state & ME_LEFT) == 0)
            {
                tryEnqueueState(state ^ (ME_LEFT | LANTERN_LEFT), state, 1);

                if ((state & ASSISTENT_LEFT) == 0)
                    tryEnqueueState(state ^ (ME_LEFT | ASSISTENT_LEFT | LANTERN_LEFT), state, 2);

                if ((state & JANITOR_LEFT) == 0)
                    tryEnqueueState(state ^ (ME_LEFT | JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) == 0)
                    tryEnqueueState(state ^ (ME_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & ASSISTENT_LEFT) == 0)
            {
                tryEnqueueState(state ^ (ASSISTENT_LEFT | LANTERN_LEFT), state, 2);

                if ((state & JANITOR_LEFT) == 0)
                    tryEnqueueState(state ^ (ASSISTENT_LEFT | JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) == 0)
                    tryEnqueueState(state ^ (ASSISTENT_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & JANITOR_LEFT) == 0)
            {
                tryEnqueueState(state ^ (JANITOR_LEFT | LANTERN_LEFT), state, 5);

                if ((state & PROFESSOR_LEFT) == 0)
                    tryEnqueueState(state ^ (JANITOR_LEFT | PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
            }

            if ((state & PROFESSOR_LEFT) == 0)
                tryEnqueueState(state ^ (PROFESSOR_LEFT | LANTERN_LEFT), state, 10);
        }
    }

    public static String stateDescription(int state)
    {
        String s = "";

        s += ((state & ME_LEFT) != 0)        ? "M" : "";
        s += ((state & ASSISTENT_LEFT) != 0) ? "A" : "";
        s += ((state & JANITOR_LEFT) != 0)   ? "J" : "";
        s += ((state & PROFESSOR_LEFT) != 0) ? "P" : "";
        s += ((state & LANTERN_LEFT) != 0)   ? "L" : "";
        s += "][";
        s += ((state & LANTERN_LEFT) == 0)   ? "L" : "";
        s += ((state & PROFESSOR_LEFT) == 0) ? "P" : "";
        s += ((state & JANITOR_LEFT) == 0)   ? "J" : "";
        s += ((state & ASSISTENT_LEFT) == 0) ? "A" : "";
        s += ((state & ME_LEFT) == 0)        ? "M" : "";
        s += " " + Integer.toString(duration[state]);

        return s;
    }

    public static void main(String[] arguments)
    {
        /* The starting state. */
        Integer state = ME_LEFT | ASSISTENT_LEFT | JANITOR_LEFT | PROFESSOR_LEFT | LANTERN_LEFT;

        Arrays.fill(duration, Integer.MAX_VALUE / 2);
        Arrays.fill(resolved, false);
        Arrays.fill(predecessor, -1);

        /* Add the starting state (situation) into the queue... */
        duration[state] = 0;
        queue.add(state);

        /* ... and until the queue gets emptied or the solution was found... */
        while ((state = queue.poll()) != null && (state &= STATE_MASK) != 0)
        {
            /* ... look for the possible evolutions of the current situation
             * and if they have not been encountered (or have been and the time
             * we can reach them improved) add them to the queue.
             *
             * NOTE that the resolved state is used here only to get around
             * the problem that priority queue does not support ``decreaseKey``
             * method.
             */
            if (!resolved[state])
            {
                resolved[state] = true;
                expandState(state);
            }
        }

        /* This should not happen, but bear in mind that in general
         * the problem might not have a solution.
         */
        if (state == null)
        {
            System.out.println("The riddle has no solution!");
        }
        else
        {
            Stack<Integer> solution = new Stack<Integer>();

            while (state >= 0)
            {
                solution.push(state);
                state = predecessor[state];
            }

            while (!solution.empty())
                System.out.println(stateDescription(solution.pop()));
        }
    }
}