Arithmetically Challenged

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Challenge 24 is a popular mathematics game used in many grade schools. In each game, contestants are given a card with four positive integers i1, i2, i3, i4 on it, and the first one who can use all of these numbers and any combination of the four basic arithmetic operations to get 24 wins. Each of the numbers i1, i2, i3, i4 must be used exactly once. Division can be used only if the divisor evenly divides the dividend (i.e., you can perform 6/2 but not 6/4). For example, if the card contains the numbers 7, 2, 5 and 1, possible solutions are (7-2)*5-1 or (7+1)*(5-2). Hmmm . . . this sounds like a source of a good programming problem.
Write a program that determines the longest consecutive sequence of integers that can be obtained by different ways of arithmetically combining the four integers. For example, with 7, 2, 5 and 1 the longest consecutive sequence is -18 to 26 (yes, we’re allowing final results to be negative). The “+” and “−” operators must be used as binary operators, not as unary signs.


Each test case will consist of a single line containing the four, not necessarily distinct, positive integers, none of which will exceed 100. A line containing four 0’s will terminate input.


For each test case, output the case number and the longest consecutive sequence of obtainable values, in the format shown in the sample output. If there is more than one longest consecutive sequence, use the one with the largest first value.

Sample Input

7 2 5 1
8 15 38 3
0 0 0 0

Sample Output

Case 1: -18 to 26
Case 2: 150 to 153




The 2009 ACM-ICPC East Central North America