COCI '15 Contest 3 #4 Slon

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, the integer P and M. Slon has to answer the following question: "What is the minimal non-negative value of variable x in expression A so that the remainder of dividing A with M is equal to P?". The solution will always exist.

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

Examples of valid expressions 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: 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 (1 \le |A| \le 100\,000).
The second line of input contains two integers P (0 \le P \le M - 1), M (1 \le M \le 1\,000\,000).
The arithmetic expression A will only consists 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

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

Sample Input 1

5+3+x
9 10

Sample Output 1

1

Explanation for Sample Output 1

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

Sample Input 2

20+3+x
0 5

Sample Output 2

2

Sample Input 3

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

Sample Output 3

1

Comments


  • 1
    kobortor  commented on Oct. 23, 2016, 9:53 p.m.

    does BEDMAS apply?


    • 0
      Kirito  commented on Oct. 23, 2016, 10:25 p.m.

      Yes.


      • 0
        kobortor  commented on Oct. 23, 2016, 11:22 p.m.

        ok


  • 1
    Kirito  commented on Oct. 2, 2016, 8:03 p.m. edited

    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, 12:01 p.m.

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

      Because I hate everyone.