DMOPC '15 Contest 7 P4 - Magic

View as PDF

Submit solution

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

Problem types
Allowed languages

Two magicians named Alice and Bob participate in a challenge. The two participate in a race on a circular track split in K equal-length sectors, determined by the points P_0, P_1, \dots, P_{K-1}.

  • Alice starts at point P_a and runs through S_a sectors per second.
  • Bob starts at point P_b and runs through S_b sectors per second.

If at any point in the race the distance between the two is less than D, Alice will use her magic to instantly push Bob a minimum distance such that the two magicians remain at a distance greater or equal to D. The winning conditions are as follows:

  • Alice wins if it is possible that sometime during the race, the sum of the shortest distance (running on the circular track) between herself to P_0 and Bob to P_0 is prime.
  • Bob wins if Alice cannot.

In a given scenario, who wins?

Input Specification

The first line of input will contain the integers K (0 < K \le 1000) and D (0 \le D < \dfrac{K}{2}).
The second line of input will contain the integers S_a and S_b.
The third line of input will contain the integers P_a and P_b.

Output Specification

Either Alice or Bob, identifying the winner.


  • S_a, S_b, P_a, P_b < K.
  • At least a turn is executed.
  • In case Alice and Bob are on the same segment, Bob is pushed behind Alice.

Sample Input

6 2
2 3
0 1

Sample Output



At the start, the positions of (\text{Alice}, \text{Bob}) are (0,1), but immediately this changes to (0, 2) as Alice pushes Bob. In the second instant, we have the positions (0+2=2, 2+3=5), such that the sum of distances to P_0 is 2+(6-5)=3. Since 3 is a prime number, Alice wins.


  • 0
    kobortor  commented on April 13, 2016, 8:47 p.m.

    When the position is (0,2), why doesn't she win?

    • 0
      bobbotboy  commented on April 13, 2016, 8:57 p.m.

      Constraints: At least a turn is executed.

      I think this means that each person must move once (by sA and sB units) before calculamatating whether prime or not.

      • 1
        kobortor  commented on April 13, 2016, 9:06 p.m.

        Then the testcase is weak, I submitted without checking if its the first run and got AC.

  • 0
    jeffreyl  commented on April 12, 2016, 6:48 p.m.

    What happens if K=0? Does Bob simply win as Alice cannot?

    • 1
      WallE256  commented on April 12, 2016, 6:51 p.m. edit 2

      During rewriting, the constraint of K was changed accidentally. So, 0 < K \le 1000. Text was changed.

  • 1
    d  commented on April 12, 2016, 5:11 p.m. edited
    100 2
    35 2
    0 10

    Edit: Alice and Bob don't really run in a continuous motion, they teleport S sectors every second.