2000 LSU Computer Science High School Programming Contest
Veteran Problem 2: Spreadsheet (Judge Copy)

• Problem Statement
• Test Data 0
• Output for Test Data 0
• Test Data 1
• Output for Test Data 1
• Test Data 2
• Output for Test Data 2
• Test Data 3
• Output for Test Data 3
• Test Data 4
• Output for Test Data 4

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Veteran Problem 2: Spreadsheet (Judge Copy)

In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It became a huge success and, at that time, was the killer application for the Apple II computers. Today, spreadsheets are found on most desktop computers.

The idea behind spreadsheets is very simple, though powerful. A spreadsheet consists of a table where each cell contains either a number or a formula. A formula can compute an expression that depends on the values of other cells. Text and graphics can be added for presentation purposes.

You are to write a very simple spreadsheet application. Your program should accept several spreadsheets. Each cell of the spreadsheet contains either a numeric value (integers only) or a formula, which only support sums. After having computed the values of all formulas, your program should output the resulting spreadsheet where all formulas have been replaced by their values.

Figure 1: Naming of the cells in the top left corner

Input

The first line of the input file contains the number of spreadsheets to follow. A spreadsheet starts with a line consisting of two integer numbers, separated by a space, giving the number of columns and rows. The following lines of the input for that spreadsheet each contain one cell. If the spreadsheet had 3 rows and 2 columns (B3 is the bottom, right cell), then this spreadsheet would have 7 lines of input:

Input		Explanation
2 3		Columns Rows
5		Cell A1
=A1+A2		Cell B1
7		Cell A2
=A1+B1+A2		Cell B2
=B2+A2		Cell A3
=A1+B2+A3+B1+A2+A1		Cell B3

A cell consists either of a numeric integer value or of a formula. A formula starts with an equal sign (=). After that, one or more cell names follow, separated by plus signs (+). The value of such a formula is the sum of all values found in the referenced cells. These cells may again contain a formula. There are no spaces within a formula.

You may safely assume that there are no cyclic dependencies between cells. So each spreadsheet can be fully computed. In other words, if A1 contains a formula referencing cell B3, B3 will NOT contain a formula that depends (directly or indirectly) on the value of the cell A1.

The name of a cell consists of one letter for the column followed by a number between 1 and 26 (inclusive) for the row. The letters for the column form the following series: A, B, C, ..., Z. These letters correspond to the numbers from 1 to 26. The top left cell has the name A1. See figure 1.

Output

The output of your program should be formatted like the spreadsheet. If the spreadsheet has 3 rows and 2 columns, then the output should have 3 rows of 2 integers (numbers on a line should be separated by at least one space). Only numeric values should be output (all formulas must be solved).

Sample Input

1
4 3
10 
34 
37 
=A1+B1+C1
40 
17 
34 
=A2+B2+C2
=A1+A2 
=B1+B2 
=C1+C2 
=D1+D2

Sample Output

10 34 37 81
40 17 34 91
50 51 71 172

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 0

1
4 3
10 
34 
37 
=A1+B1+C1
40 
17 
34 
=A2+B2+C2
=A1+A2 
=B1+B2 
=C1+C2 
=D1+D2

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 0

  10  34  37  81
  40  17  34  91
  50  51  71 172

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 1

0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 2

2
5 4
1 
1 
1 
=A1+C1 
=B1+B1
2 
2 
2 
=A2+B2+C2 
=B2
22 
18 
14 
15 
=A3+B3+C3+D3
=A1+B2 
=C3+B1 
=D3+A2 
=A3+B3+C3 
18
1 1
89

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 2

   1   1   1   2   2
   2   2   2   6   2
  22  18  14  15  69
   3  15  17  54  18
  89

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 3

3
4 2
89 
98 
88 
99
76 
67 
77 
66
2 4
18 
99
=A1+B1 
17
=B1+B2 
=A1
22 
33
3 3
1 
2 
3
=A1+A1+A1 
8 
9
=A1+B1 
=B2+B1 
=A1+B1+C1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 3

  89  98  88  99
  76  67  77  66
  18  99
 117  17
 116  18
  22  33
   1   2   3
   3   8   9
   3  10   6

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 4

2
2 3
5
=A1+A2
7
=A1+B1+A2
=B2+A2
=A1+B2+A3+B1+A2+A1
2 3
5
=A1+A2
7
=A1+B1+A2
=B2+A2
=A1+B2+A3+B1+A2+A1
2 3
5
=A1+A2
7
=A1+B1+A2
=B2+A2
=A1+B2+A3+B1+A2+A1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 4

   5  12
   7  24
  31  84
   5  12
   7  24
  31  84

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.