Pencils from the 19th Century

Time limit1sMemory limit128 MB

Summary
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 NN, a man buys NN pencils for NN 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 NN (2≤N≤2562 \le N \le 256). The input ends with a line containing 00, which is not processed. There are at most 32 cases.

Output

For each case, first print the line "Case kk:", where kk is the case number starting from 1, followed by the line "NN pencils for NN 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 aa is the number of four-cent pencils, bb is the number of pencils sold two for a penny, and cc is the number sold four for a penny. Within a case, order the solutions by increasing aa; once aa is fixed, bb and cc 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.

Examples1

  1. Example 1

    Input
    10
    20
    40
    0
    
    Expected output
    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