Before “automaton” was a theoretic computer science concept, it meant “mechanical figure or contrivance constructed to act as if by its own motive power: robot.” Examples include fortunetellers but could also describe a pencil seller, moving pencils from several baskets to a delivery trough.
On National Public Radio, the Sunday Weekend Edition program has a “Sunday Puzzle” segment. The show that aired on Sunday, 29 June 2008, had the following puzzle for listeners to respond to (by Thursday, 3 July, at noon through the NPR web site):
One clarification from the program of 6 July: correct solutions contain at least one of each pencil type. For our purposes, we will expand on the problem, rather than just getting 20 pencils for 20 cents (which is shown in the sample output below). The input file will present a number of cases. For each case, give all solutions or print the text “No solution found”. Solutions are to be ordered by increasing numbers of four-cent pencils.
Case n: nn pencils for nn cents nn at four cents each nn at two for a penny nn at four for a penny
|Sample Input||Sample Output|
10 20 40 0
Case 1: 10 pencils for 10 cents No solution found. Case 2: 20 pencils for 20 cents 3 at four cents each 15 at two for a penny 2 at four for a penny Case 3: 40 pencils for 40 cents 6 at four cents each 30 at two for a penny 4 at four for a penny 7 at four cents each 15 at two for a penny 18 at four for a penny