COCI '15 Contest 3 #4 Slon

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 64M

Problem types

A student called Slon is very mischievous in school. He is always bored in class and he is always making a mess. The teacher wanted to calm him down and "tame" him, so he has given him a difficult mathematical problem.

The teacher gives Slon an arithmetic expression $A$ ~A~, the integer $P$ ~P~ and $M$ ~M~. Slon has to answer the following question: "What is the minimal non-negative value of variable $x$ ~x~ in expression $A$ ~A~ so that the remainder of dividing $A$ ~A~ with $M$ ~M~ is equal to $P$ ~P~?". The solution will always exist.

Additionally, it will hold that, if we apply the laws of distribution on expression $A$ ~A~, variable $x$ ~x~ will not multiply variable $x$ ~x~ (formally, the expression is a polynomial of the first degree in variable $x$ ~x~).

Examples of valid expressions $A$ ~A~: $5 + x \cdot (3 + 2), x + 3 \cdot x + 4 \cdot (5 + 3 \cdot (2 + x - 2 \cdot x))$ .
Examples of invalid expressions $A$ ~A~: $5 \cdot (3 + x \cdot (3 + x)), x \cdot (x + x \cdot (1 + x))$ .

Input Specification

The first line of input contains the expression $A$ ~A~ $(1 \le |A| \le 100\,000)$ ~(1 \le |A| \le 100\,000)~.
The second line of input contains two integers $P$ ~P~ $(0 \le P \le M-1)$ ~(0 \le P \le M-1)~, $M$ ~M~ $(1 \le M \le 1\,000\,000)$ ~(1 \le M \le 1\,000\,000)~.
The arithmetic expression $A$ ~A~ will only consist of characters +, -, *, (, ), x and digits from 0 to 9.
The brackets will always be paired, the operators +, - and * will always be applied to exactly two values (there will not be an expression (-5) or (4+-5)) and all multiplications will be explicit (there will not be an expression 4(5) or 2(x)).

Output Specification

The first and only line of output must contain the minimal non-negative value of variable $x$ ~x~.

Sample Input 1

5+3+x
9 10

Sample Output 1

Explanation for Sample Output 1

The remainder of dividing $5+3+x$ ~5+3+x~ with $10$ ~10~ for $x = 0$ ~x = 0~ is $8$ ~8~, and the remainder of division for $x = 1$ ~x = 1~ is $9$ ~9~, which is the solution.

Sample Input 2

20+3+x
0 5

Sample Output 2

Sample Input 3

3*(x+(x+4)*5)
1 7

Sample Output 3

Comments

1

kobortor commented on Oct. 24, 2016, 1:53 a.m.

does BEDMAS apply?

0

Kirito commented on Oct. 24, 2016, 2:25 a.m.

Yes.

0

kobortor commented on Oct. 24, 2016, 3:22 a.m.

ok

1

Kirito commented on Oct. 3, 2016, 12:03 a.m. ← edit 2 →

There are two new cases (case 11 and 12), courtesy of d. Each case is worth 25% of all points.

16

ZQFMGB12 commented on Oct. 3, 2016, 4:01 p.m. ← edited →

I asked d why he wanted to add extra test cases and he told me:

Because I hate everyone.