eolymp
bolt
Try our new interface for solving problems
Problems

Identity Checker

Identity Checker

You likely have seen that \textbf{x(sin^2 x + cos^2 x) − x = 0}, and you may have seen that \textbf{sin(2x) − 2 sin xcos x = 0}. But did you know that \textbf{tan} \textbf{(2x)(x − x tan^2 x) − 2x tan x = 0}? Would you believe that \textbf{sin (2x) − 2 cos x = 0}? That last one is false, but don’t just take our word for it; you should write a program that determines whether an algebraic expression simplifies to zero (whenever it is defined). \InputFile The input consists of multiple test cases, each on one line. Each test case starts with an integer \textbf{n}, the number of tokens that describes a formula. The next \textbf{n} tokens describe a formula in reverse polish notation. The notation works as follows. There is a stack that begins empty, and the following commands manipulate the contents of the stack: \begin{itemize} \item "\textbf{x}" pushes the variable \textbf{x} to the stack. \item "\textbf{sin}", "\textbf{cos}", and "\textbf{tan}" replace the top element of the stack with its \textit{sin}, \textit{cos}, and \textit{tan}, respectively. \item "\textbf{+}", "\textbf{-}", and "\textbf{*}" replace the top two elements of the stack (\textbf{a} on top, followed by \textbf{b}) with their \textbf{sum} \textbf{(b + a)}, \textbf{difference (b − a)}, and \textbf{product (b ∗ a)}, respectively. \end{itemize} You may assume that the input is valid, and results in a single item on the stack, which is the desired expression. The length of a line will be at most \textbf{300} characters. Function arguments can contain functions, so \textbf{x sin sin} is valid, but the recursion will not go any deeper than this. The input terminates with a line with \textbf{n} = \textbf{0}. \OutputFile For each test case, print out a single line that contains "\textbf{Identity}" if the expression is always zero, and "\textbf{Not an identity}" otherwise (quotes added for clarity).
Time limit 1 second
Memory limit 122.17 MiB
Input example #1
15 x sin x sin * x cos x cos * + x * x -
16 x sin x cos * x sin x cos * + x x + sin -
24 x x + tan x x tan x tan * x * - * x tan x * - x tan x * -
10 x x + sin x cos - x cos -
0
Output example #1
Identity
Identity
Identity
Not an identity
Source 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011