Even Odd Game
시간 제한4초메모리 제한1024 MB
두 사람이 +k 또는 *k 카드를 번갈아 사용해 시작값에서 공용 수를 갱신하고, 최종 값이 홀수면 선공이 이긴다. 누가 먼저 둘지와 어떻게 두어야 Eve가 이기는지 결정하는 게임이다.
문제
As every Saturday, Eve is paying her local game club a visit. Today, Bob has brought a new game he has designed on his own. After thorough investigation, you claim that there exists a dominant strategy, so one player can always win. Bob is hesitant to accept that his game is boring to play, so he challenges you to play a round! Since you claim that there exists a dominant strategy, you may determine who begins the game.
Figure E.1: The cards in the two sample interactions.
The rules are as follows. There are cards on the table, each containing a maths operation (+ or *) and an integer, as shown in Figure E.1. Eve and Bob alternate picking cards to manipulate a common number using one of the cards. For instance, if the current value of the number is , and the card says , then the value gets updated to . Each card can only be used once, and the game ends when all the cards have been used. The player who makes the first move wins if the final number is odd, and the other player wins if the final number is even. Given the list of cards and the starting value, help Eve win the game.