Expressions

Time limit1sMemory limit128 MB

Summary

For each range of digits and target, print every fully bracketed expression over the digits in order that evaluates to the target. (Note: summary must be one sentence, at most 160 chars.)

Level: Hard8 of 10
Topics: Backtracking, Recursion, Brute force, Implementation
Solved: No attempts yet

Problem

You are helping to design a new card game whose goal is to give children practice with mental arithmetic. Each card shows a contiguous range of one-digit numbers together with a target integer. A player must combine those one-digit numbers, used in the order shown, into an expression whose value equals the target.

The four allowed binary operators are addition +, subtraction -, multiplication *, and modulus % (the remainder). The game's designer is a computer scientist and deliberately chose modulus as the fourth operation instead of the division you might expect. Brackets may be used freely to control the order of evaluation.

Given a contiguous range of digits chosen from 1, 2, 3, 4, 5, 6, 7, 8 (the digit 9 is never used) and a target integer, find every way to write the target as such an expression over the digits in order.

For example, with the range 1..4 and the target 10, one valid expression is (((1+2)+3)+4) = 10. It is not the only one — several other expressions also evaluate to 10.

Input

The input is a sequence of problems. Each problem is given on one line as three integers A B C:

A and B describe the range of digits, with $1 \le A \le B \le 8$ ; the digits used are A, A+1, …, B in that order.
C is the target value.

The input ends with a line containing three zeros (0 0 0), which must not be processed.

Output

For each problem, first print a line

Problem #n: A..B => C

where n is the problem number, counting from 1. Then print one line for every expression that evaluates to the target value C.

Every expression is fully bracketed: a pair of brackets encloses each operator together with its two operands (a lone single digit is written without brackets). Only valid expressions are printed; an expression that performs a modulus by zero is not valid.

Arithmetic uses ordinary integer rules: the modulus result a % b takes the sign of its left operand a (as in C/C++), for example (1-2)%3 evaluates to -1.

The expressions must be printed in the following order:

By bracketing pattern. Scanning left to right, a digit comes before an opening bracket, so (1+(… comes before ((1+….
By operator, within the same bracketing pattern. Scanning left to right, + comes before *, which comes before -, which comes before %. For instance (1+(2+… comes before (1+(2*…, which comes before (1*(2+…, which comes before (1*(2*….

Examples1

Example 1

Input

1 4 10
2 2 2
0 0 0

Expected output

Problem #1: 1..4 => 10
(1+(2+(3+4)))
(1+((2+3)+4))
(1*((2*3)+4))
((1+2)+(3+4))
((1+(2+3))+4)
((1*(2*3))+4)
(((1+2)+3)+4)
(((1*2)*3)+4)
Problem #2: 2..2 => 2
2