DMOPC '15 Contest 7 P4 - Magic

View as PDF

Submit solution

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

Author:
Problem types

Two magicians named Alice and Bob participate in a challenge. The two participate in a race on a circular track split into 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.

Constraints

  • 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

Alice

Explanation

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 (6-2)+(6-5)=5. Since 5 is a prime number, Alice wins.


Comments


  • 0
    kobortor  commented on April 14, 2016, 12:47 a.m. edited

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


    • 0
      bobbotboy  commented on April 14, 2016, 12:57 a.m. edited

      Constraints: At least a turn is executed.

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


      • 1
        kobortor  commented on April 14, 2016, 1:06 a.m.

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


  • 1
    d  commented on April 12, 2016, 9: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.