Since we only care about the parity of the value ~x~, we can consider taking ~x~ and all ~a_i~ values modulo ~2~. Additionally, since any remaining number can be taken from the list, we do not care about its order. In other words, We only need to consider the amount of even and odd values in the list.

Subtask 1

In this subtask, all values in the list are odd.

Consider the player who gets the last turn. The final number in the list that they must use on this turn is guarenteed to be odd. Let this number be ~k~.

If they choose to update ~x~ to ~x+k~, the parity of ~x~ will flip from even to odd or vice versa.

If they choose to update ~x~ to ~x\times k~, the parity of ~x~ will stay the same.

Thus, they have complete control over the parity of ~x~. Since this is the final turn, they can force the parity of ~x~ to be whatever is needed for them to win.

The player who gets the last turn is determined by the parity of ~N~. Thus, if ~N~ is odd, Steven wins. Otherwise, if ~N~ is even, Todd wins.

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

Subtask 2

We once again consider two cases based on the parity of ~N~.

Case 1: ~N~ is odd

Since ~N~ is odd, Steven gets the last turn. Let the final number in the list that he must use on this turn be ~k~.

If ~k~ is odd, then as shown in Subtask 1, Steven has complete control over the parity of ~x~ and can force it to be even, winning the game.

If ~k~ is even, Steven can choose to update ~x~ to ~x \times k~, which will also force ~x~ to be even, winning the game.

So, no matter what number ~k~ remains in the list, Steven can always force ~x~ to be even.

Thus, if ~N~ is odd, Steven always wins.

Case 2: ~N~ is even

Since ~N~ is even, Todd gets the last turn.

Consider Steven's final turn before this last turn. As shown in Case 1, he can always force ~x~ to be even after his turn no matter what number ~k~ he uses from the list.

Note that it may be possible for Steven to make ~x~ odd after this second last turn. However, it is never optimal, since Todd will always be able to win if ~x~ is odd on his final turn using the following strategy:

• If ~k~ is odd, then Todd can choose to update ~x~ to ~x \times k~, so as to keep ~x~ odd.
• If ~k~ is even, then Todd can choose to update ~x~ to ~x + k~, which also keeps ~x~ odd.

Thus, we can assume that Steven will always force ~x~ to be even before Todd's final turn.

Now, Todd can only win if the final number ~k~ remaining in the list is odd.

• If ~k~ is odd, then Todd can choose to update ~x~ to ~x + k~, flipping ~x~ from even to odd.
• If ~k~ is even, then both ~x + k~ and ~x \times k~ are even numbers, and Todd has no choice but to lose.

We can now infer that Steven's strategy leading up to the final turn is to use up as many odd numbers as possible so that Todd does not have an odd number as his final remaining number. Similarly, Todd's strategy leading up to the final turn is to first use up all the even numbers to potentially have an odd number saved for his final turn.

Since Steven has ~N/2~ turns in total, he can use up at most ~N/2~ odd numbers. Thus, if the amount of odd numbers in the starting list is strictly greater than ~N/2~, Steven will not be able to use up all the odd numbers and Todd can save an odd number for his final turn, winning the game.

Summary

Todd wins if and only if ~N~ is even and the amount of odd numbers in the starting list is strictly greater than ~N/2~. Otherwise, Steven wins.

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

Bonus

Author Commentary

This was indeed a leftover problem idea from UTS Open '24. However, in the old version, I wanted Steven and Todd to place ~+~ and ~\times~ signs in between numbers of a fixed sequence and to evaluate the final expression with order of operations. That turned out to be too hard for me to solve, so here we are.

Reference Solution

https://dmoj.ca/src/7502665