295C — Greg and Friends

Note that at each step we are interested in only the position of the boat (number of banks) and the number of people 50 and 100 weight on each shore. With that number of people on one side is completely determined by the other. To find the minimum number of crossings will be used wave algorithm based on this condition. To find the number of ways to add just the sum of all transitions in the state transition will move all the way from one state to another by multiplying the number of ways to choose the people who need to move from one state to another

(quote)