Source file: | multiply.{c, cpp, java} |
Input file: | multiply.in |
Educators are always coming up with new ways to teach math to students. In 2011, an educational software company, All Computer Math (ACM), developed an application to display products in a traditional grade school math format. ACM is now working on an updated version of the software that will display results in a lattice format that some students find to be easier when multiplying larger numbers.
An example would be when multiplying 345 * 56 = 19320 as given below, using a lattice grid with 2 rows and 3 columns, which appears inside a surrounding frame:
+---------------+ | 3 4 5 | | +---+---+---+ | | |1 /|2 /|2 /| | | | / | / | / |5| |1|/ 5|/ 0|/ 5| | | +---+---+---+ | |/|1 /|2 /|3 /| | | | / | / | / |6| |9|/ 8|/ 4|/ 0| | | +---+---+---+ | |/ 3 / 2 / 0 | +---------------+
The first operand, 345, is displayed above the top of the grid
with each digit centered horizontally above its column of the grid,
and the second operand, 56, is displayed along the righthand side
with each digit centered vertically at the center of its row in the
grid. A single cell of the grid, such as
+---+
|3 /|
| / |
|/ 0|
+---+
represents the product of the digit of the first operand that is above
its column and the digit of the second operand that is to the right of
its row. In our example, this cell represents the product
The overall product is then computed by summing along the
diagonals in the lattice that represent the same place
values in the result. For example, in our first problem the product
19320 was computed as:
1's digit | = 0 |
10's digit | = 5 + 3 + 4 = 12, thus 2 with a carry of 1 |
100's digit | = (1 carry) + 2 + 0 + 2 + 8 = 13, thus 3 with a carry of 1 |
1000's digit | = (1 carry) + 2 + 5 + 1 = 9 |
10000's digit | = 1 |
To provide an aesthetic
view, we use a series of
Leading zeros should be displayed within lattice grid cells, but
leading zeros should never be displayed in the product, nor should
there ever be a
+-----------+
| 1 2 |
| +---+---+ |
| |0 /|0 /| |
| | / | / |2|
| |/ 2|/ 4| |
| +---+---+ |
| |0 /|1 /| |
| | / | / |7|
|3|/ 7|/ 4| |
| +---+---+ |
|/ 2 / 4 |
+-----------+
Note that in the top-right grid of the lattice, the product 2 * 2 = 04
is displayed with the zero for the tens digit. However, there is no
thousands digit displayed in the product 324, nor is there any slash
displayed above the digit 3 in that product.
Input: The input contains one or more tests. Each
test contains two positive integers, A and B, such that
Output: For each data set, produce the grid that illustrates how to multiply the two numbers using the lattice multiplication technique.
Note: The tables must be formatted precisely as
outlined by the rules and examples provided. Mistakes that involve
solely errant whitespace will be categorized as
Example Input: | Example Output: |
345 56 12 27 1 68 9999 7 3 3 0 0 |
+---------------+ | 3 4 5 | | +---+---+---+ | | |1 /|2 /|2 /| | | | / | / | / |5| |1|/ 5|/ 0|/ 5| | | +---+---+---+ | |/|1 /|2 /|3 /| | | | / | / | / |6| |9|/ 8|/ 4|/ 0| | | +---+---+---+ | |/ 3 / 2 / 0 | +---------------+ +-----------+ | 1 2 | | +---+---+ | | |0 /|0 /| | | | / | / |2| | |/ 2|/ 4| | | +---+---+ | | |0 /|1 /| | | | / | / |7| |3|/ 7|/ 4| | | +---+---+ | |/ 2 / 4 | +-----------+ +-------+ | 1 | | +---+ | | |0 /| | | | / |6| | |/ 6| | | +---+ | | |0 /| | | | / |8| |6|/ 8| | | +---+ | |/ 8 | +-------+ +-------------------+ | 9 9 9 9 | | +---+---+---+---+ | | |6 /|6 /|6 /|6 /| | | | / | / | / | / |7| |6|/ 3|/ 3|/ 3|/ 3| | | +---+---+---+---+ | |/ 9 / 9 / 9 / 3 | +-------------------+ +-------+ | 3 | | +---+ | | |0 /| | | | / |3| | |/ 9| | | +---+ | | 9 | +-------+ |