"Memo" Game With a Hint

시간 제한2초메모리 제한2048 MB

요약
카드 뒷면의 회전 표시로 추가 정보를 부호화해, 메모 게임에서 평균 13.5회 이하의 실수로 끝내는 전략을 설계한다.
난이도

어려움10점 중 8점

유형
조합론, 그리디, 확률, 수학
정답자
아직 제출이 없습니다

문제

"Memo", or "Memory", is a game with cards. In this problem, the game uses 25 pictures, and each picture is printed on exactly two rectangular cards: so, there are 50 cards in total. Initially, all cards are randomly shuffled and dealt face down, so that the pictures are not visible. The cards occupy positions which are numbered by integers from 11 to 5050.

Vasilisa trains her memory by playing "Memo". She makes moves in the game. Each move consists of two actions. For the first action, Vasilisa picks a position with a card face down and turns it face up. For the second action, she picks another such position and also turns the card face up. If the two pictures on these cards are the same, they remain face up. Otherwise, they are both turned face down again, and Vasilisa gets a miss.

Vasilisa wins when all cards are face up. Her task is to win and get as little misses as possible.

Vasilisa has trained her memory well and devised a good strategy, and now, in each game, she makes approximately 14.83 misses on average. To make things more interesting, she called her sister Sasha to play together.

The backs of the cards are all the same, but they look differently when the card is rotated 180 degrees without turning it face up. Now Sasha and Vasilisa play as follows. Firstly, Sasha shuffles the cards and deals them face up. Then she turns them face down, but for each card, she can either rotate it 180 degrees, or not rotate. Finally, Vasilisa initially sees not only 50 cards with the same backs, but for each card, she sees whether it is rotated 180 degrees.

Devise a way for Sasha and Vasilisa to agree how the cards are rotated, so that Vasilisa can win with no more than 13.5 misses on average.

예제2

  1. 예제 1

    입력
    prepare
    2
    ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXY
    
    AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYY
    
    
    예상 출력
    
    
    
    00000000000000000000000001111111111111111111111111
    
    11010011001111111111111111111111111111111111111010
    
  2. 예제 2

    입력
    play
    2
    00000000000000000000000001111111111111111111111111
    
    A.
    
    E-
    
    A.
    
    A+
    (...)
    
    Y.
    
    Y!
    11010011001111111111111111111111111111111111111010
    
    E.
    
    E+
    (...)
    
    A.
    
    A!
    
    예상 출력
    
    
    
    1
    
    5
    
    26
    
    1
    
    (...)
    25
    
    50
    
    
    10
    
    9
    
    (...)
    1
    
    2