Cells
InterviewTime limit1sMemory limit1024 MB
Given formulas with cell references and the operators + - * /, compute every cell's value and print them sorted by cell name.
Problem
Tim loves spreadsheets. Everything he does on a computer, he does in a spreadsheet. Track his expenses? Create a spreadsheet! Pick which car to buy? Create a spreadsheet to compare them! Make an inventory of his games? Create a spreadsheet! Decide which girl he loves most? ...
Unfortunately, his spreadsheet software just crashed. He needs some of the data right now and has no time to install a competing office suite.
Given the formulas in the cells of a spreadsheet, calculate the values of all the cells.
When evaluating an expression, usual priorities apply: first evaluate all * and / (left to right), then all + and - (left to right).
You may assume the expressions are such that, when evaluated in the correct order, the result and all intermediate values fit into 32-bit signed integer variables.
The operator / is integer division, always rounded down. The dividend is always non-negative and the divisor is always positive.
Input
The first line contains an integer T, the number of test cases. Each test case is preceded by a blank line.
Each test case starts with a single number N, the number of expressions. Each of the following N lines contains one cell formula of the form CELL = EXPRESSION, where CELL is the cell name and EXPRESSION is a mathematical expression made of cell names and the operators +, -, * and /. A cell name is a non-empty sequence of letters followed by a positive integer. The length of a cell name is at most 5.
Each test case is valid: there are no cycles, and every cell referenced in an expression has a definition.
Output
For each test case, output the calculated values of the cells, one per line, in the form CELL = VALUE. Rows are sorted alphabetically. To compare two rows, find the first character where they differ. The row with the smaller ASCII value comes first.