No.3496 協力カード当て
タグ : / 解いたユーザー数 14
作問者 :
注意
ジャッジが不安定な面がありましたら対処します。
問題文
概要
カードの最大値を $M$、各プレイヤーの手札枚数を $N$ とします。
値 $v$ ($1 \leq v \leq M$) のカードが $v$ 枚ずつ、合計 $\frac{M(M+1)}{2}$ 枚のカードがあります。
この中から $3N$ 枚を選び、3人のプレイヤー A, B, C にそれぞれ $N$ 枚ずつ配ります(使われないカードもあります)。
A と B は協力チーム(コミュニケーション問題: 同じプログラムが2プロセスで動作)です。
C はジャッジが操作し、質問しません。
A と B は自分の手札だけを知っています。ゲームマスターに値を質問して、C の手札を当ててください。
ルール
- 値 $v$ のカードは全体で $v$ 枚存在する
- $3N$ 枚が選ばれ、A, B, C に $N$ 枚ずつ配られる(残りは使われない)
- A → B → A → B → ... の順にターンが交互に回る
- 自分のターンでは
ASK X(質問)またはGUESS c1 ... cN(回答)のどちらかを出力する ASK X: ゲームマスターが「値 $X$ は3人の手札に合計 $K$ 枚」を全員に通知するGUESS: C の手札を回答する。A, B 両方が正解すれば AC
判定
スコアは1ケース $ 3M - Q$ です($Q$=質問回数)。質問が少ないほど高スコアです。
テストケースは16ケースあります。
入出力はすべて整数です。
- 両プレイヤーの GUESS が両方正解 → AC(スコア=$Q$)
- 片方でも不正解 → WA
- 条件に合わない値を出力 → WA
- 質問数が $3M$ を超えた → QLE
入力
初期化
ジャッジから以下を受信します:
$id$ $N$ $M$ $c_1$ $c_2$ ... $c_N$
- $id$: プレイヤー番号($1$=A, $2$=B)
- $N$: 手札枚数、$M$: カードの最大値
- $c_i$: 自分の手札(昇順ソート済み)
各ターン
自分のターン: TURN を受信 → ASK X または GUESS c1 c2 ... cN を出力
相手のターン: WAIT を受信(出力不要、結果を待つ)
質問結果: COUNT X K が両プレイヤーに通知される
回答結果: GUESSED id ok が両プレイヤーに通知される($ok$: 1=正解, 0=不正解)
終了: 両プレイヤーが GUESS した後、END Q を受信($Q$=質問回数)
制約
- 入出力はすべて整数
- $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 Xは $1 \leq X \leq M$ を満たすことGUESSはちょうど $N$ 個の整数(各 $1$ 〜 $M$)を昇順ソート順で出力すること- 最大質問数: $3M$
出力
プロトコルに従ってインタラクティブに入出力してください。
各出力は flush するようにしてください
サンプル
サンプル1
N=2, M=4, A の手札: [1, 3]、B の手札: [3, 4]、C の手札: [2, 3]
| # | アクティブ | Player A 入力 | Player A 出力 | Player B 入力 | Player B 出力 | 解説 |
|---|---|---|---|---|---|---|
| 1 2 4 1 3 | 2 2 4 3 4 | 初期化。A=[1,3], B=[3,4] | ||||
| 1 | A | TURN | ASK 1 | WAIT | Aが値1を質問 | |
| COUNT 1 1 | COUNT 1 1 | 場に1が1枚 | ||||
| 2 | B | WAIT | TURN | ASK 2 | Bが値2を質問 | |
| COUNT 2 1 | COUNT 2 1 | 場に2が1枚 | ||||
| 3 | A | TURN | ASK 3 | WAIT | ||
| COUNT 3 3 | COUNT 3 3 | 場に3が3枚 | ||||
| 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が回答 | |
| GUESSED 1 1 | GUESSED 1 1 | 正解 | ||||
| 10 | B | WAIT | TURN | GUESS 2 3 | Bが回答 | |
| GUESSED 2 1 | GUESSED 2 1 | 正解 | ||||
| END 8 | END 8 | 質問数8, AC |
※ この例は最適とは限りません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。