아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Adversarial Memory

시간 제한4초메모리 제한512 MB

요약
카드를 뒤집을 때마다 보이는 숫자를 마술사가 정할 수 있는 기억 게임에서, 최소 2n-1번의 차례가 필요하도록 만드는 전략을 찾는다.
난이도

보통10점 중 7점

유형
그리디, 게임 이론, 구현, 조합론
정답자
아직 제출이 없습니다

문제

Charlie is playing a game of memory (also known as concentration) on his own. The game consists of 2n2n cards, where each of the numbers from 11 to nn 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 2n−12n-1 turns to finish the game.

More formally, there are 2n2n indices from 11 to 2n2n. In a turn, Charlie chooses an index ii and turns over the card at index ii. You can then decide what number Charlie will see when he turns over the card. Then Charlie will choose a different index jj and turn over the card at index jj. 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.

예제2

  1. 예제 1

    입력
    1
    1
    
    2
    
    
    예상 출력
    
    
    1
    
    1
    
  2. 예제 2

    입력
    3
    1
    
    2
    
    3
    
    2
    
    4
    
    5
    
    5
    
    1
    
    4
    
    6
    
    
    예상 출력
    
    
    1
    
    2
    
    2
    
    2
    
    3
    
    1
    
    1
    
    1
    
    3
    
    3