Subtask 1

Note that the Duke can only touch the piles with ~2~ stones, while Alice can only touch those with ~1~. Furthermore, if the Duke selects a pile with ~2~ stones, he should always take all the stones in that pile (if he only takes ~1~ stone, he essentially gives Alice an extra turn). Thus, we can simply compare the number of piles with ~1~ and ~2~ stones to determine who wins the game.

Time Complexity: ~\mathcal{O}(N)~

Subtask 2

Let's look a bit more into the optimal strategy for each player. We say the Duke controls a pile if it contains an even number of stones, and Alice controls a pile if it contains an odd number of stones. The number of moves each player can make is based on the piles which they control. Thus, clearly, it is never optimal to take an odd number of stones from any pile for any player, since it gives control of the pile to the other player (an exception is Alice taking ~1~ stone from a pile with only ~1~ stone).

Moreover, each player would like to maximize the number of moves they can make, which is equivalent to minimizing the number of stones they take from any pile while still keeping it under control. Thus, we can deduce that it is always optimal for both players to take ~2~ stones on each turn. From these conclusions, we see that simply summing up the ceiling of half the number of stones in each pile a player controls and comparing these values will tell us the winner of the game.

Time Complexity: ~\mathcal{O}(N)~