問題一覧 > 通常問題

No.1830 Balanced Majority

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 73
作問者 : rianoriano / テスター : chineristACchineristAC 👑 ygussanyygussany
7 ProblemId : 7549 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-23 18:54:04

問題文

この問題はインタラクティブ形式です。

$N$ 枚のカードが積み上げられた山札があります。ただし、$N$ は偶数とします。 山札の中のカードは表裏バラバラな状態ですが、全体で $N/2$ 枚（ちょうど半分）が表向きであることが分かっています。

これから $20$ 回以下の任意の回数、下記の形式の質問を行うことで

  • 山札の中で連続している「$N/2$ 枚以上 $N$ 枚未満」のカードの組であって、含まれる表向きのカードの枚数と裏向きのカードの枚数が等しいもの
を一つ見つけてください。なお、この問題の制約下で条件を満たす組は必ず存在することが示せます。

【質問の形式】
$1\leq K\leq N$ を満たす任意の整数 $K$ を毎回好きに選び、「山札の上から $K$ 枚目までに含まれる表向きのカードの枚数」を尋ねる。

制約

  • $4\leq N\leq 2\times 10^5$
  • $N$ は偶数である
  • 入力は全て整数である

入出力

最初の入力 
$N$

質問を行う場合の出力 

$?$ $K$
$1\leq K\leq N$ である必要があり、質問は各テストケースごとに $20$ 回以下である必要があります。

質問に対しての返答の入力 
$S$
ただし $S$ は、質問された $K$ に対する「山札の上から数えて $K$ 枚目までのカードの中で表向きであるものの枚数」です。 また、質問が不正あるいは $20$ 回を超過した場合には $-1$ が入力されます。この場合、直ちにプログラムを終了してください。

回答を行う際の出力 
$!$ $L$ $R$
山札の中で上から数えて $L$ 枚目から $R$ 枚目までのカードの組（両端を含む）が条件を満たす組であると判明したとき、上記のように答えてください。 ただし $1\leq L \leq R\leq N$ である必要があります。

全ての出力に対して、最後に flush してください。そうでない場合、ジャッジの結果は不定です。 また、各記号および数字の間は空白で区切るようにしてください。

入出力のコード例（ C++ / Python / C ）: クリックで展開
C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    //入力
    int N; cin >> N;
    
    //質問
    int K = N,S;
    cout << "? " << K << endl;
    cin >> S;
    
    //回答
    int L = 1,R = N;
    cout << "! " << L << " " << R << endl;
}
Python
import sys

##入力
N = int(input())

##質問
K = N
print("? {}".format(K))
sys.stdout.flush()
S = int(input())

##回答
L = 1; R = N
print("! {} {}".format(L,R))
sys.stdout.flush()
C
#include <stdio.h>

int main(){
    //入力
    int N;
    scanf("%d", &N);
	
    //質問
    int K = N,S;
    printf("? %d\n", K);
    fflush(stdout);
    scanf("%d", &S);
	
    //回答
    int L = 1,R = N;
    printf("! %d %d\n", L, R);
    fflush(stdout);
}

サンプル

サンプル1

以下のようなやり取りが考えられます。

入力出力説明
6$N=6$
? 1$K=1$ で質問
1$1$ 枚目までに含まれる表向きのカードは $1$ 枚
? 2$K=2$ で質問
2$2$ 枚目までに含まれる表向きのカードは $2$ 枚
? 3$K=3$ で質問
2$3$ 枚目までに含まれる表向きのカードは $2$ 枚
? 4$K=4$ で質問
2$4$ 枚目までに含まれる表向きのカードは $2$ 枚
! 1 4$1$ 枚目から $4$ 枚目の組が条件を満たすと回答
質問として $K=1,2,3,4$ を選んでおり、ここまでの結果からカードの状態は $1$ 枚目から順に「表、表、裏、裏」と分かります。 したがって、残る $2$ 枚の状態は分かりませんが、$4$ 枚の組として $1,2,3,4$ 枚目が確実に条件を満たしますので $L=1,R=4$ を出力しています。
なお、$2,3$ 枚目や $1,2,3,4,5,6$ 枚目といった組は枚数の条件に反するため誤答となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。