QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB

#19601. Los iguales son iguales

Statistics

El Sr. Simpson se levantó con una ligera sensación de cansancio. Comenzaba otro día de trabajo duro. Un montón de trabajos esperaba su revisión en el escritorio de su oficina. Contenían las respuestas de sus alumnos a preguntas de matemáticas, pero parecían simples manchas de tinta.

Su dolor de cabeza se debía a la «creatividad» de sus alumnos. Le habían presentado muchas formas de responder a cada problema. Él tiene su propia respuesta, correcta por supuesto y la mejor desde su punto de vista estético.

Algunos alumnos escribieron expresiones algebraicas equivalentes a la respuesta esperada, pero con una forma literal muy distinta de la del Sr. Simpson. Otros escribieron expresiones no equivalentes que parecían muy similares. Solo unas pocas respuestas eran exactamente iguales a la suya.

Su deber es comprobar si cada expresión es matemáticamente equivalente a la respuesta preparada. Así evita que expresiones equivalentes se marquen como «incorrectas», aunque no sean aceptables según su criterio estético.

Ya había dedicado cinco días a comprobar las expresiones. De repente se levantó y gritó: «¡Ya he tenido suficiente! Debo pedir ayuda».

Tu tarea es escribir un programa que ayude al Sr. Simpson a decidir si cada respuesta equivale a la «correcta». Las expresiones de los trabajos son polinomios multivariables sobre los símbolos $a,b,\ldots,z$, con coeficientes enteros, por ejemplo $(a+b^2)(a-b^2)$, $ax^2+2bx+c$ y $(x^2+5x+4)(x^2+5x+6)+1$.

El Sr. Simpson introducirá cada expresión tal como está escrita en los trabajos. Promete que una expresión algebraica es una secuencia de términos separados por operadores aditivos + y -, que representa la suma de los términos con dichos operadores, si los hay. Un término es una yuxtaposición de factores que representa su producto. Un factor es (a) un entero no negativo como secuencia de cifras decimales, (b) un símbolo de variable, una de las letras minúsculas de a a z, posiblemente seguido del símbolo ^ y una cifra no nula que representa la potencia de la variable, o (c) una expresión algebraica entre paréntesis, definida recursivamente. Los operadores + y - solo aparecen como operadores binarios, nunca como operadores unarios para indicar el signo de un operando.

Dice que pondrá uno o más espacios antes de un entero si este sigue inmediatamente a otro entero o a una cifra que siga al símbolo ^. También puede poner espacios en distintos lugares de una expresión para hacerla legible, pero nunca entre dos cifras consecutivas de un entero. Las expresiones no son tan complicadas: al reemplazar sus signos - por +, no tendrán ninguna variable elevada a la potencia $10$ ni un coeficiente mayor que mil millones, incluso si se expanden completamente como suma de productos de coeficientes y potencias de variables.

Entrada

La entrada es una secuencia de bloques de líneas. Un bloque consta de líneas que contienen una expresión cada una y una línea de terminación. Después del último bloque hay otra línea de terminación. Una línea de terminación contiene únicamente un punto.

La primera expresión de un bloque está preparada por el Sr. Simpson; todas las siguientes son respuestas de alumnos. Una expresión consta de letras minúsculas, cifras, operadores +, -, ^, paréntesis (, ) y espacios. Una línea con una expresión no tiene más de 80 caracteres.

Salida

Para cada respuesta de un alumno, el programa debe producir una línea que contenga únicamente yes o no, según sea o no matemáticamente equivalente a la respuesta esperada. Después de cada bloque, debe producir una línea que contenga únicamente un punto.

Ejemplos

Entrada 1

a+b+c
(a+b)+c
a-(b-c)+2
.
4ab
(a - b)(0-b+a) - 1a ^ 2 - b ^ 2
2 b 2 a
.
108 a
2 2 3 3 3 a
4 a^1 27
.
.

Salida 1

yes
no
.
no
yes
.
yes
yes
.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.