14615 - Big Orange Cat's Polynomial II   

Status  |  Limits Submit

Description

Given multiple polynomials made of fractions, like F(x) = +2/3x^2 -3/4x +1/2, G(x) = +2/5x -1/3, in the format:
<sign><|fraction|>x^<power>, with positive/negative signs shown.

To support polynomial addition and multiplication, implement the incomplete functions in two classes: Fraction and Polynomial.

This problem is a partial judge.
Please implement functions defined in the header file:

class Fraction:
Fraction operator +(const Fraction& other); // Add two fractions and simplify to the lowest terms.
Fraction operator *(const Fraction & other); // Multiply two fractions and simplify to the lowest terms.

class Polynomial:
Polynomial(int deg, const Fraction *coeffs); // constructor
Polynomial operator+(const Polynomial& other) const; // Add two polynomials.
Polynomial operator*(const Polynomial& other) const; // Multiply two polynomials.
Polynomial& operator=(const Polynomial& other); //  Assigns one polynomial to another
Fraction evaluate(Fraction x) const; // Evaluates polynomial at given value x

The definition of a simplified fraction: a fraction whose numerator (分子) and denominator (分母) have a GCD of 1. 

If the coefficient becomes 0 after adding two polynomials, still output it as +0, e.g: F = +2/3^x -10/1, G = -2/3^x +10/1, F + G should be +0/1^x +0/1

Input

The first line contains two positive integers n and m, where n is the number of polynomials, and m is the number of operations to perform

The next n lines describe the polynomials. Each line is in one of two formats:

  1. <symbol> = <polynomial>, which defines the mathematical expression for that polynomial (e.g., "F = 2x^2 + 3x + 1").
  2. <symbol1> = <symbol2>, which means the polynomial defined by <symbol1> is the same as the polynomial defined by <symbol2>.
The next m lines each contain an operation in the format <func1> <op> <func2> <x>, where:
  • <func1> and <func2> are the names of two polynomials.
  • <op> is an operator, which can be + or *, indicating the operation to perform (addition, or multiplication).
  • <x> is the value of x to substitute into the polynomials

Constraints

  • The degree of each polynomial is at most 5.
  • 1 <= n <= 26
  • 1 <= m <= 1000
  • All numbers are between -5 and 5, and the denominator is not 0.
  • The symbol will only consist of a single uppercase letter.

Subtasks

  • testcase 1 ~ 2: The operation will only involve addition (+)
  • testcase 3 ~ 4: The operation will only involve multiplication (*)
  • testcases 5 ~ 6: No additional restrictions

Hint

You can use __gcd(a, b) with #include <algorithm> to calculate the greatest common divisor of two numbers, but please pay attention to the sign.

Output

For each operation, you need to output the result in the format <poly> = <ans>, where:
  • <poly> is the mathematical expression of the resulting polynomial after performing the operation on <func1> and <func2>.
  • <ans> is the value of the resulting polynomial evaluated at x = x.
  • If a polynomial has a coefficient of 0, represent it as +0/1.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14615.cpp

Partial Judge Header

14615.h

Tags




Discuss