printРабочее место участника

printЗадачи

708. Equation

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Your task is to solve an equation of the form `f(x)\ =\ 0` where `f(x)` is written in postfix notation with numbers, operations +, -, *, /, and at most one occurrence of a variable `x`.
For example, `f(x)` for an equation `(4x+2)/2\ =\ 0` is written as:
4 X * 2 + 2 /
The solution for `f(x)\ =\ 0` is `x\ =\ -1/2`.
Input
The input file consists of a single line with at most 30 tokens separated by spaces. Each token is either:
  • a digit from 0 to 9;
  • an operation +, -, *, or /;
  • an uppercase letter X that denotes variable `x`.
The input file contains a correct representation of `f(x)` in postfix notation where token X occurs at most once. There is no division by a constant zero in this equation, that is, there always exists a value of `x`, such that `f(x)` can be evaluated without division by zero.
Output
Write to the output file:
  • X = `p//q` if equation `f(x)\ =\ 0` has a single solution that can be represented with a simple fraction `p/q`, where `p` and `q` are coprime integer numbers and `q` is positive.
  • NONE if equation `f(x)\ =\ 0` has no solution;
  • MULTIPLE if equation `f(x)\ =\ 0` has multiple solutions.

Sample input 1

4 X * 2 + 2 /

Sample output 1

X = -1/2

Sample input 2

2 2 *

Sample output 2

NONE

Sample input 3

0 2 X / *

Sample output 3

MULTIPLE
Source: ACM ICPC NEERC 2007
loading