DMOPC '21 Contest 1 P1 - Partial Game - Olympiads Online Judge

DMOPC '21 Contest 1 P1 - Partial Game

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

The Duke of Death suffers from the horrible condition of killing anything that he touches. Thus, to pass time, he likes to play games involving inanimate objects with his maid Alice. One such game involves $N$ ~N~ piles of stones, with $A_i$ ~A_i~ stones in the $i$ ~i~-th pile. The Duke and Alice take turns making moves, with the Duke going first:

On the Duke's turn, if there is at least one non-empty pile with an even number of stones, then he should choose one of those piles and remove any positive number of stones from that pile. Otherwise, he does nothing and passes the turn to Alice.

Similarly, on Alice's turn, if there is at least one non-empty pile with an odd number of stones, then she should choose one of those piles and remove any positive number of stones from that pile. Otherwise, she does nothing and passes the turn to the Duke.

The game ends when there are no stones left in any pile, and the player who took the last stone is declared the winner. If both players play optimally, who has a winning strategy? A player has a winning strategy if they can guarantee their win regardless of what their opponent chooses to do. In this game, we can prove that one of the players always has a winning strategy.

Constraints

$1 \le N \le 2 \times 10^5$ ~1 \le N \le 2 \times 10^5~

$1 \le A_i \le 10^9$ ~1 \le A_i \le 10^9~

Subtask 1 [20%]

$1 \le A_i \le 2$ ~1 \le A_i \le 2~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer $N$ ~N~, the number of piles.

The next line contains $N$ ~N~ integers $A_i$ ~A_i~ $(1 \le i \le N)$ ~(1 \le i \le N)~, the number of stones in each pile.

Output Specification

Output Duke if the Duke has a winning strategy, or Alice if Alice has a winning strategy.

Sample Input 1

4
2 1 2 2

Sample Output 1

Duke

Explanation for Sample 1

For example, one instance of a game could go as follows:

The Duke takes $1$ ~1~ stone from pile $1$ ~1~, changing the number of stones in each pile to $[1, 1, 2, 2]$ ~[1, 1, 2, 2]~.
Alice takes $1$ ~1~ stone from pile $2$ ~2~, changing the number of stones in each pile to $[1, 0, 2, 2]$ ~[1, 0, 2, 2]~.
The Duke takes $2$ ~2~ stones from pile $4$ ~4~, changing the number of stones in each pile to $[1, 0, 2, 0]$ ~[1, 0, 2, 0]~.
Alice takes $1$ ~1~ stone from pile $1$ ~1~, changing the number of stones in each pile to $[0, 0, 2, 0]$ ~[0, 0, 2, 0]~.
The Duke takes $2$ ~2~ stones from pile $3$ ~3~, changing the number of stones in each pile to $[0, 0, 0, 0]$ ~[0, 0, 0, 0]~.

In this case, the Duke took the last stone, so he is the winner. In general, we can prove that the Duke has a winning strategy here, so we output Duke.

Sample Input 2

3
1 4 1

Sample Output 2

Alice

Explanation for Sample 2

As another example, the game could proceed as follows:

The Duke takes $1$ ~1~ stone from pile $2$ ~2~, changing the number of stones in each pile to $[1, 3, 1]$ ~[1, 3, 1]~.
Alice takes $1$ ~1~ stone from pile $2$ ~2~, changing the number of stones in each pile to $[1, 2, 1]$ ~[1, 2, 1]~.
The Duke takes $2$ ~2~ stones from pile $2$ ~2~, changing the number of stones in each pile to $[1, 0, 1]$ ~[1, 0, 1]~.
Alice takes $1$ ~1~ stone from pile $3$ ~3~, changing the number of stones in each pile to $[1, 0, 0]$ ~[1, 0, 0]~.
The Duke passes the turn to Alice.
Alice takes $1$ ~1~ stone from pile $1$ ~1~, changing the number of stones in each pile to $[0, 0, 0]$ ~[0, 0, 0]~.

In this case, Alice took the last stone, so she is the winner. In general, we can prove that Alice has a winning strategy here, so we output Alice.

Comments

3

MarsFlat commented on Sept. 11, 2021, 3:37 a.m. ← edited →

If you require assistance on this problem, it happens to have an editorial readily available if you are stuck.

It's also recommended to join the discord for further assistance as wait times are often less and it does not clog the comments section.

1

William_Tian1 commented on Sept. 10, 2021, 2:20 p.m.

you might have to use long for the second part

-3

dchoo333 commented on Sept. 10, 2021, 11:38 p.m. ← edited →

What do you mean? I'm trying to solve this so it could be helpful.

2

Nils_Emmenegger commented on Sept. 11, 2021, 12:26 a.m. ← edited →

They are referring to using 64-bit integers instead of 32-bit integers to prevent integer overflow. This isn't a concern if you are using a language that handles this automatically like Python or JavaScript, but it does matter for (among many others) Java and C++.

-3

dchoo333 commented on Sept. 11, 2021, 1:00 a.m.

What is wrong with my Batch #2 Case #2?