Solved by 3 users: UdH-WiNGeR, defrager, Dest.
UserDateAttemptTimeCMSC
defrager`11 apr 2009`C++9500.072754
UdH-WiNGeR`10 mar 2009`Java5100.883036
Dest`09 jun 2010`C++200.033527
 C++ 2 Java 1
` >  >  >  >  >  >  >  >  >  > `

## Reduction to common denominator

Time limit = 4 second(s)

Input is sum of polynomial ratios. You should output equal expression of one of the forms:

"p(x)/q(x)" or "p(x)" or "0",

where p(x) ans q(x) are polynomials with integer coefficients. and GCD(p(x), q(x) ) == 1.

Input. World from the following grammar:

``` S ::=  NUMBER
| R ( ('+' | '-')  R)*
NUMBER := <integer number less then 10000 in moduli >
PNUMBER := <positive integer number less then 1000>
R ::= A ('/' A)?
A ::= NUMBER
| 'x' ('^' PNUMBER)?
| '(' NUMBER ')'
| '(' C (('+' | '-') C)* ')'
C ::=  (NUMBER '*')? 'x' ('^' PNUMBER)?
```

Examples of derived words (from symbol S):

``` 1, --3+45--6,  -x/(2*x),  x^100/x^11, 13/x + x2 — x/(x-1), (13*x-2)/(26*x-4)
```

Legth of input data is less then 1000. All coefficients during calculations stay less then 2000000000 in their moduli. Number of ratios is less then 26.

Priority of operand '^' is the highest. Next are "*" and "/" . And operands "+" and "-" have the lowest priority.

Operands '+', '-', '/', '*' are left-associate. So in expression a-b-c (where a, b, c are words derived from R or A) calculation sequence is defined by the parentheses: ((a-b)-c).

Output. Output expression (equal to given one) of one of the folowing forms: "0" or "p(x)" or "(p(x))/(q(x))".

Expression "x1" should be outputed as "x". Expression "A*x0" should be outputed as "A", where A is integer number. Expression "x0" should be outputed as "1".

Main term of denominator should have positive coefficient.

 Input#1```1/x + x ``` Output#1```(x^2+1)/(x) ```
 Input#2```(1+x)/(x^2-1)+1 ``` Output#2```(x)/(x-1) ```
 Input#3```(-x^4--1)/(1+x^2+x+x^3) ``` Output#3```-x+1 ```
 Input#4```x+x-3*x-1/(5*x) ``` Output#4```(-5*x^2-1)/(5*x) ```
 Input#5```1-1/x^17+(x^13-1)/(x^26-1) ``` Output#5```(x^30+2*x^17-x^13-1)/(x^30+x^17) ```

Author:
Classic problem. Tests and descriptions by Artem Voroztsov.
25 ноября 2006

 © acm.mipt DevGroupThe page was generated in 200ms