시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 31 6 6 19.355%

문제

Two players are going to demonstrate a card trick with a standard 52-card deck. For convenience card values will be distinct integers from 0 to 51.

Cards are initially placed on a table in a single row face up (with values visible) in some order unknown to the players.

The first player goes to the table, looks at the cards and does swaps, at most 𝑺 times in total. Each swap is performed by choosing two cards on positions i and j (i and j can be equal) and moving the card from position i to position j and vice versa.

After that the first player leaves without communicating with the second player and all the cards are turned over (their values are no longer visible) without changing their order. The second player is invited to the table and is asked to guess where the card with target value is and is allowed to turn over at most T cards one by one. If any of the revealed cards is target, then the players win. If they run out of guesses they lose.

Your goal is to write two programs that will simulate the actions of the players and win the game.

제한

  • 1 ≤ S ≤ 52
  • 1 ≤ T ≤ 51
  • 0 ≤ target < 52

구현

You will be provided with two programs - FirstPlayer and SecondPlayer along with sample grader.

In FirstPlayer you have to implement the following function:

void swapCards(int cards[], int S, int T)
  • This function is called exactly once by the grader
  • cards: an array containing initial card values from left to right, with exactly 52 elements indexed from 0 through 51
  • S: the number of allowed swaps
  • T: the number of allowed guesses

swapCards can make calls to the following function:

void doSwap(int i, int j)
  • i: index of first card to swap, 0 ≤ i < 52
  • j: index of second card to swap, 0 ≤ j < 52
  • doSwap can be called at most S times

In SecondPlayer you have to implement the following function:

void guessCard(int S, int T, int target)
  • S: the number of allowed swaps
  • T: the number of allowed guesses
  • target: the card value that should be revealed

guessCard can make calls to the following function:

int guess(int idx)
  • idx: guessed index, 0 ≤ idx < 52
  • It returns the value of the idx-th card
  • guess can be called at most T times.
  • when the correct guess happens the evaluation terminates successfully

예제

Below is an example of input for the attached grader.

The first line should contain two integers: S and T.

The second line should contain 52 numbers. i-th one denoting the value of the i-th card.

The third like contains an integer target.

Sample Input to grader

1 51
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
1
Sample Calls
Calls sub-calls Returns
swapCards([0,1,…], 1, 51)    
  doSwap(0, 1)  
    swaps cards with indexes 0 and 1
swapCards finishes    
guessCard(1, 51, 1)    
  guess(5)  
    5
  guess(1)  
    0
  guess(0)  
    Correct!

서브태스크

번호 배점 제한
1 16

S = 52, T = 1

2 20

S + T = 52

3 22

S = 13, T = 27

4 18

S = 1, T = 26

5 24

Winning strategy exists for given S and T

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.