Pencils from the 19th Century
Time limit1sMemory limit128 MB
For each N, find all triples (a, b, c) of positive counts of 4-cent, 2-for-1, and 4-for-1 pencils with a+b+c = N and 4a + b/2 + c/4 = N.
- Level
Easy3 of 10
- Topics
- Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
Before "automaton" became a concept in theoretical computer science, it meant "a mechanical figure or device built to act as if by its own motive power; a robot." A fortune-telling doll is one example, but the term could also describe a mechanical pencil seller that moved pencils from several baskets into a delivery trough to sell them.
A radio quiz program once posed the following puzzle to its listeners:
From a 19th-century trade card advertising a remedy for coughs and colds: A man buys 20 pencils for 20 cents and receives three kinds of pencils. Some pencils cost four cents each, some are two for a penny (one cent), and the rest are four for a penny. How many pencils of each type does the man receive?
A later clarification added one rule: a correct solution must contain at least one pencil of each type.
We generalize the puzzle beyond buying 20 pencils for 20 cents. For a given integer , a man buys pencils for cents using the same three kinds of pencils (four cents each, two for a penny, and four for a penny), and includes at least one pencil of each kind. Your program handles several such cases. For each case, print every solution, or print "No solution found." if there is none. Within a case, order the solutions by increasing number of four-cent pencils.
Input
Each line contains a single integer (). The input ends with a line containing , which is not processed. There are at most 32 cases.
Output
For each case, first print the line "Case :", where is the case number starting from 1, followed by the line " pencils for cents". Then print the solutions.
Each solution is printed in the following three-line format:
<a> at four cents each
<b> at two for a penny
<c> at four for a penny
where is the number of four-cent pencils, is the number of pencils sold two for a penny, and is the number sold four for a penny. Within a case, order the solutions by increasing ; once is fixed, and are also determined. Separate consecutive solutions with a blank line. If a case has no solution, print the single line "No solution found." instead. Separate consecutive cases with a blank line.