Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
SHEET
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 367Accepted: 146

Description

See if a spreadsheet has a consistent formulation.
Any given cell of a spreadsheet can have a formula that depends on the value from some other cell. Before trying to calculate the value of a cell it is important to determine if the definition of the formula for that cell is circular.

Our spreadsheet only has a limited formulation for expressions:
definition := cell "=" expression

expression := term | expression "+" term | expression "-" term
term := factor | term "*" factor | term "/" factor
factor := number | cell | "(" expression ")"
number := digit | number digit
digit := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
cell := "R" digit digit "C" digit digit

Valid cell rows and columns are 1 through 20, so that a total of 400 cells are available in our spreadsheet.

Input

The input will contain one or more lines, each representing cells that are defined in the spreadsheet.
Note that, if an expression in some cell refers to some other cell, the contents of that other cell will always be defined.There are no white space characters in the expressions.

Output

A single line is printed for each cell defined in the input(and in the same order). This should be the cell name followed by "circular" if evaluating the cell results in a circular definition (either directly or indirectly). If the cell can be evaluated without a circular definition, then the word "ok" should follow the cell.

Sample Input

R01C01=1
R01C02=2
R01C03=R01C01+R01C02
R02C01=(R03C02+1)*R01C03
R03C02=R02C01

Sample Output

R01C01 ok
R01C02 ok
R01C03 ok
R02C01 circular
R03C02 circular

Hint

Clarification
The following spreadsheet would have two circular results

R01C01=0*R01C01
R02C01=R02C01-R02C01

Point is, don\'t do algebraic simplifications before determining circularity.

Q. If a cell references a cell that is circular, is the cell defined as circular even though it does not reference itself?

A. Yes.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator