Adversarial Memory
시간 제한4초메모리 제한512 MB
카드를 뒤집을 때마다 보이는 숫자를 마술사가 정할 수 있는 기억 게임에서, 최소 2n-1번의 차례가 필요하도록 만드는 전략을 찾는다.
문제
Charlie is playing a game of memory (also known as concentration) on his own. The game consists of cards, where each of the numbers from to is written on exactly two cards. The cards are upside down on the table. In a turn, Charlie turns over one card, looks at it, and then turns over another card. If the cards have the same number, they are removed from the game. Otherwise, they are turned back over and placed back. The goal of the game is to remove all the cards from the game in as few moves as possible.
You are a magician, and hence you are able to change the numbers on upside down cards seamlessly. If Charlie turns over the same card twice, you need to make sure that he sees the same number both times, or else Charlie would notice something is wrong. You also need to make sure that for each number there will be exactly two cards on which Charlie will see that number. Your goal is to force Charlie to need at least turns to finish the game.
More formally, there are indices from to . In a turn, Charlie chooses an index and turns over the card at index . You can then decide what number Charlie will see when he turns over the card. Then Charlie will choose a different index and turn over the card at index . You can then decide what number Charlie will see when he turns over that card. The only restrictions are that Charlie must always see the same number when he turns over the same card, and that for each number there will be exactly two cards on which Charlie will see that number. Note that Charlie will never choose the index of a card that is already out of the game.