No.3496 Cooperative Card Guessing
Note
If the judge turns out to be unstable in any way, we will deal with it.
Problem Statement
Overview
Let $M$ be the maximum card value and $N$ be the number of cards in each player's hand.
For each value $v$ ($1 \leq v \leq M$), there are $v$ cards of that value, for a total of $\frac{M(M+1)}{2}$ cards.
From these, $3N$ cards are chosen and dealt to three players A, B, and C, with $N$ cards each (some cards may go unused).
A and B form a cooperative team (communication problem: the same program runs as 2 processes).
C is operated by the judge and does not ask questions.
A and B know only their own hands. Ask the game master about values and determine C's hand.
Rules
- A card of value $v$ exists in exactly $v$ copies overall
- $3N$ cards are chosen and dealt to A, B, and C, with $N$ cards each (the rest are unused)
- Turns alternate in the order A → B → A → B → ...
- On your turn, output either
ASK X(a question) orGUESS c1 ... cN(an answer) ASK X: the game master notifies everyone that "there are $K$ cards of value $X$ in total among the three players' hands"GUESS: answer C's hand. If both A and B are correct, the verdict is AC
Judging
The score for one case is $ 3M - Q$ ($Q$ = the number of questions). The fewer the questions, the higher the score.
There are 16 test cases.
All input and output values are integers.
- Both players' GUESSes are correct → AC (score=$Q$)
- Even one of them is incorrect → WA
- A value violating the conditions is output → WA
- The number of questions exceeds $3M$ → QLE
Input
Initialization
You receive the following from the judge:
$id$ $N$ $M$ $c_1$ $c_2$ ... $c_N$
- $id$: player number ($1$=A, $2$=B)
- $N$: the number of cards in hand, $M$: the maximum card value
- $c_i$: your own hand (sorted in ascending order)
Each Turn
Your turn: receive TURN → output ASK X or GUESS c1 c2 ... cN
The other player's turn: receive WAIT (no output needed; wait for the result)
Question result: COUNT X K is sent to both players
Answer result: GUESSED id ok is sent to both players ($ok$: 1=correct, 0=incorrect)
End: after both players have made a GUESS, you receive END Q ($Q$=the number of questions)
Constraints
- All input and output values are integers
- $id \in \{1, 2\}$
- $2 \leq N \leq 18$
- $4 \leq M \leq 11$
- $1 \leq c_i \leq M$
- $3N \leq \frac{M(M+1)}{2}$
ASK Xmust satisfy $1 \leq X \leq M$GUESSmust output exactly $N$ integers (each from $1$ to $M$) in ascending sorted order- Maximum number of questions: $3M$
Output
Perform input and output interactively according to the protocol.
Make sure to flush after each output.
Sample
Sample 1
N=2, M=4, A's hand: [1, 3], B's hand: [3, 4], C's hand: [2, 3]
| # | Active | Player A Input | Player A Output | Player B Input | Player B Output | Explanation |
|---|---|---|---|---|---|---|
| 1 2 4 1 3 | 2 2 4 3 4 | Initialization. A=[1,3], B=[3,4] | ||||
| 1 | A | TURN | ASK 1 | WAIT | A asks about value 1 | |
| COUNT 1 1 | COUNT 1 1 | There is 1 card of value 1 in play | ||||
| 2 | B | WAIT | TURN | ASK 2 | B asks about value 2 | |
| COUNT 2 1 | COUNT 2 1 | There is 1 card of value 2 in play | ||||
| 3 | A | TURN | ASK 3 | WAIT | ||
| COUNT 3 3 | COUNT 3 3 | There are 3 cards of value 3 in play | ||||
| 4 | B | WAIT | TURN | ASK 4 | ||
| COUNT 4 1 | COUNT 4 1 | |||||
| 5 | A | TURN | ASK 2 | WAIT | ||
| COUNT 2 1 | COUNT 2 1 | |||||
| 6 | B | WAIT | TURN | ASK 1 | ||
| COUNT 1 1 | COUNT 1 1 | |||||
| 7 | A | TURN | ASK 4 | WAIT | ||
| COUNT 4 1 | COUNT 4 1 | |||||
| 8 | B | WAIT | TURN | ASK 3 | ||
| COUNT 3 3 | COUNT 3 3 | |||||
| 9 | A | TURN | GUESS 2 3 | WAIT | A answers | |
| GUESSED 1 1 | GUESSED 1 1 | Correct | ||||
| 10 | B | WAIT | TURN | GUESS 2 3 | B answers | |
| GUESSED 2 1 | GUESSED 2 1 | Correct | ||||
| END 8 | END 8 | 8 questions, AC |
* This example is not necessarily optimal.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。