Limits
1s, 256 MB

Mita’s team had always been a good team when it came to competitive programming, and this year, their hard work and dedication had finally paid off. They got selected for the ICPC regional competition. It was a momentous occasion, and they knew they had to give it their all to succeed.

In preparation for the upcoming ICPC regional competition, Mita’s team decided to engage in friendly practice sessions. In one practice contest, they found an interesting problem about two players passing through two paths having obstacles.

The problem statement is as follows:

Two paths having $N \: (1 \: to \: N)$ points are given for players $A$ and $B$. Both players will start traveling at the same time from point $1$. These paths contain obstacles at different points. If any player encounters an obstacle at an even-numbered point, they must move back $1$ step, while encountering an obstacle at an odd-numbered point requires them to move back $2$ steps. Once a player encounters an obstacle, it becomes inactive and will not impact that player’s move again. Traveling to every point requires $1$ second.

The player who reaches point $N$ before another player will win the game. If both players reach point N at the same time, the game is considered a tie.

As you are one of the teammates, help your teammates determine who will win the game or whether the game will be tied.

It is guaranteed that there are no obstacles at points $1$ and $N$.

The first line provides a single integer $N$, which represents the number of points on two paths. The second line consists of two integers, $X$ and $Y$. These indicate the number of obstacles on the paths for players $A$ and $B$ respectively. The third line contains $X$ integers, $a_1,a_2,…,a_x$, representing the positions of obstacles on player $A’s$ path. The fourth line contains $Y$ integers, $b_1,b_2,…,b_y$, representing the positions of obstacles on player $B’s$ path.

$3 \leq N \leq 10^5$

$0 \leq X, Y \leq N-2$

$1 < a_i < N$

$1 < b_i < N$

For each test case print $“A”$ without quote if player $A$ wins the game, or print $“B”$ without quote if player $B$ wins the game, or print $“DRAW”$ without quote if the game is tied.

Input | Output |
---|---|

10 2 4 2 4 2 5 6 9 | A |

For the first test case, let's simulate the moves for player $A$: Player $A$ starts at point 1. Player $A$ reaches point 2 in 1 second. Player $A$ encounters an obstacle at point 2 and moves back one step to point 1 in 1 second. Player $A$ reaches point 2 (again) in 1 second. Player $A$ reaches point 3 in 1 second. Player $A$ reaches point 4 in 1 second. Player $A$ encounters an obstacle at point 4 and moves back one step to point 3 in 1 second. Player $A$ reaches point 4 (again) in 1 second.
From this point on, player $A’s$ path has no obstacles. Player $A$ reaches point 10 in a total of 13 seconds. In the same way, Player $B$ reaches point 10 in a total of 21 seconds. Since, player $A$ reaches point 10 before player $B$, therefore, the output is $"A"$ because Player $A$ wins the game. |

Input | Output |
---|---|

10 4 2 2 5 6 9 2 4 | B |

Input | Output |
---|---|

10 4 4 2 5 6 9 2 5 6 9 | DRAW |

Be careful about the newline(‘**\n**’) at the end.

Login to submit.

72%
Solution Ratio

Reyad.1935Earliest,

Tahmidul.4404Fastest, 0.0s

Tahmidul.4404Lightest, 5.1 MB

faheeedShortest, 492B

Toph uses cookies. By continuing you agree to our Cookie Policy.