One Extra Digit

From Maryville College CS Wiki
Jump to: navigation, search

This problem was part of the CCSCSE 2014 problem set. (It was problem 4, and is used here without permission based on the forgiveness model.)

Problem Statement

Bob is a great bookkeeper. But there is one mistake he occasionally makes. While adding up a long list of numbers, he sometimes types and extra stray digit in a two-digit number maing it an erroneous three-digit number. For example, the number 82 might be mistyped as 862 due to the extra stray digit 6. As a result, his sums are noticeably a little too high. In the case of typing 862 instead of 82, his sum would be off by the difference, i.e. 862-82 = 780.

Let's write a program to help Bob find his error. That is to say, if Bob knows by how much his sum is off, there should be some way of figuring out which three digit number(s) could potentially be the two digit number that has an extra digit. let's assume that when Bob computes a sum, he only makes this error once.

Definitions:

  • A two-digit number is an integer n where 10\leq n \leq 99
  • A three-digit number is an integer n where 100\leq n \leq 999.

An instance of this problem will be a number d, representing the difference between the correct and incorrect sum. This number d will be a positive integer, and will equal n_3-n_2, where n_2 is a two-digit number and n_3 is a three-digit number, and n_3 can be obtained from n_2 by the appending of an additional digit(0-9) either at the beginning, middle, or end of n_2. For example, the digit 6 could be appended into the number 82 to produce the three possible numbers 682, 862, and 826 depending on whether the 6 is put at the beginning, middle, or end.

An example instance of this problem is where d=780. Then a possible value for n_3 is 826 and its corresponding value of n_2 would be 82. In this case the 6 was concatenated to the end of n_2 to produce n_3. Note that many possible values of n_3 could exist for a particular value of d. In other words, each problem instance could have several solutions. It's also possible to have no solution.


Input

Your program should be written so that it can process several instances (i.e. test cases) of this problem. The first line of the input will give you T, the number of test cases. Assume that T\geq 1. Each of the next T lines of the input will give a value for d. In your output, you need to identify the test case number, and all solutions of that test case. Print each solution to a test case on its own line. A solution will be specified in the form n_3 - n_2 = d. print one space on either side of the minus sign, and one space on either side of the equals sign. Also format your solutions so that they are indented by two spaces. See the example I/O below.

Output

If there is more than one solution to a test case, then your solutions must be sorted in ascending order of n_3. Within a test case, do not print the same solution more than once. If a test case has no solution, then you should print "No solution for d= <value of d>" where the value of d appears after the equals sign. As with a bona fide solution, this statement should also be indented two spaces.

Sample Input

4
682
390
81
207

Output

Test case 1
  757 - 75 = 682
Test case 2
  430 - 40 = 390
  431 - 41 = 390
  432 - 42 = 390
  433 - 43 = 390
  434 - 44 = 390
  435 - 45 = 390
  436 - 46 = 390
  437 - 47 = 390
  438 - 48 = 390
  439 - 49 = 390
Test case 3
  No solution for d = 81
Test case 4
  229 - 22 = 207
  230 - 23 = 207

Solutions

Programming team, post your solutions to the following page: progTeam:One_Extra_Digit_Solutions