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))$ $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))$ $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 \leq | A | \leq 100 000)$ .
The second line of input contains two integers $P$ $P$ $(0 \le P \le M-1)$ $(0 \leq P \leq M - 1)$ , $M$ $M$ $(1 \le M \le 1\,000\,000)$ $(1 \leq M \leq 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

Copy

5+3+x
9 10

Sample Output 1

Copy

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

Copy

20+3+x
0 5

Sample Output 2

Copy

Sample Input 3

Copy

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

Sample Output 3

Copy

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.

17

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.