<PREV Problem:
NEXT>
Solved by 3 users: UdH-WiNGeR, defrager, Dest.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 23.20.13.165