Problem E (ACM ICPC Philippines 2007)

ACM ICPC Philippines 2007
First Philippine National Inter-Collegiate Programming Competition
20 October 2007, De La Salle Canlubang
Organized by the Computing Society of the Philippines
in cooperation with Association for Computing Machinery

Problem E: Factor Factory
(Input File: pe.in)

The general form of a univariate polynomial is anxn + an-1xn-1 + … + a1x + a0 where:

1. n is the degree of the polynomial and is a non-negative integer
2. anxn, an-1xn-1, …, a1x, a0 are called terms of the polynomial
3. an, an-1, …, a1 are called coefficients of the terms, and an is the leading coefficient of the polynomial
4. a0 is a constant

A monomial is a polynomial with only one term.

Write a program that completely factors (based on the rules given) polynomials that are in terms of x, with maximum degree of 100, and having integer coefficients and/or constants within the range -100 to 100. Monomial factors should not be factored further. Non-monomial factors should be factored further if and only if they have polynomial factor/s of degree 1, or they can be factored as a difference of 2 squares, difference of 2 cubes, or sum of 2 cubes.

Input:

The file consists of several test cases, each with a case number and the polynomial to be factored. The symbol ^ denotes exponentiation. Assume the terms in a polynomial are arranged in decreasing degree and there are no spaces between the characters.

Output:

For each of the test cases, output the factored polynomial, where:1. Each factor should be enclosed in a parenthesis (unless there’s only 1 factor) without spaces between the characters.2. Each factor should have exponents, coefficients, and/or constants in integer form only3. The factors should be arranged from the lowest degree to highest degree; factors of the same degree need not be arranged in a particular order.4. The terms in each factor should be arranged in decreasing degree.5. Non-monomial factors should have positive leading coefficients.

Sample Input:

Case 1: 3x^3–3
Case 2: –x^5+4x
Case 3: 4x^2+8x+4
Case 4: 2x^3+11x^2 + 17x+6
Case 5: –6x^2

Sample Output:

Case 1: (3)(x–1)(x^2+x+1)
Case 2: (–x)(x^2+2)(x^2–2)
Case 3: (4)(x+1)(x+1)
Case 4: (x+3)(x+2)(2x+1)
Case 5: –6x^2