## 4 - Pencils from the 19th Century

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):

From a 19th century trade card advertising Bassetts
Horehound Troches, a remedy for coughs and colds: A
man buys 20 pencils for 20 cents and gets three
kinds of pencils in return. Some of the pencils cost
four cents each, some are two for a penny and the rest
are four for a penny. How many pencils of each type
does the man get?

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.

### Input

Each line gives a value for

**N** (

**2 <
N < 256**), and your program is to end when

**N=0** (at most 32 problems).

### Output

The first line gives the instance, starting from 1,
followed by a line giving the statement of the
problem. Solutions are shown in the three-line
format below followed by a blank line, or the
single line “No solution found”, followed by a
blank line. Note that by the nature of the
problem, once the number of four-cent pencils
is determined, the numbers of half-cent and
quarter-cent pencils are also determined.

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 |