Polynomials P25002


Statement
 

pdf   zip

html

Many polynomials can be written as the product of several factors, where each one of them is itself a polynomial with integer coefficients. In general, this decomposition can be made in many different ways. For instance,

2x4 − 3x3 + x2 − 9x − 15   =   (x3 + x2 + 3x + 3)(2x − 5) =   (x2 + 3)(x + 1)(2x − 5)   .

Given two products of polynomials with integer coefficients, please tell if they represent the same polynomial.

Input

Input consists of several cases. Every case has two decompositions of a polynomial, each on one line. The format is exactly as shown in the sample input. The terms inside each factor are given in decreasing order. The terms with coefficient zero are omitted. The degree of every factor is at most 9. No factor is zero. The coefficients are not larger than 109 in absolute value. The represented polynomials have degrees not larger than 1000, and coefficients not larger than 10100 in absolute value.

Output

For every case, print “yes” if the two polynomials are the same, or “no” otherwise.

Public test cases
  • Input

    (+ 2x^4 - 3x^3 + 1x^2 - 9x^1 - 15x^0)
    (+ 1x^3 + 1x^2 + 3x^1 + 3x^0)(+ 2x^1 - 5x^0)
    (+ 1x^3 + 1x^2 + 3x^1 + 3x^0)(+ 2x^1 - 5x^0)
    (+ 1x^2 + 3x^0)(+ 1x^1 + 1x^0)(+ 2x^1 - 5x^0)
    (+ 1x^2 + 3x^0)(+ 1x^1 + 1x^0)(+ 2x^1 - 5x^0)
    (+ 1x^3 - 1x^2 + 3x^1 - 3x^0)(+ 2x^1 - 5x^0)
    (+ 1x^4 - 1x^0)
    (+ 1x^2 - 1x^0)(+ 1x^2 + 1x^0)
    (+ 50000x^0)(- 20000x^0)
    (- 1000000000x^0)
    (+ 1000000000x^8)(- 1000000000x^8)
    (- 1000000000x^7)(+ 1000000000x^9)
    

    Output

    yes
    yes
    no
    yes
    yes
    yes
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30