链接: https://cses.fi/problemset/task/3305

板块: Interactive Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一场编程竞赛中有 $n$ 名来自芬兰的选手和 $n$ 名来自瑞典的选手。竞赛结束后发现，每名选手都有一个互不相同的分数。

你的任务是求出竞赛中第 $k$ 高的分数。

为此，你可以进行提问：选择一个国家（芬兰或瑞典）和一个整数 $i$，评测机将告诉你该国第 $i$ 高的分数。

输入

这是一个交互题。你的程序将通过标准输入和输出与评测机进行交互。你应当先读取两个整数 $n$ 和 $k$。

在你的回合中，你可以输出以下内容之一：

• F i，其中 $1 \le i \le n$：询问芬兰第 $i$ 高的分数。
• S i，其中 $1 \le i \le n$：询问瑞典第 $i$ 高的分数。
• ! s：报告第 $k$ 高的分数为 $s$。输出此行后你的程序必须终止。

每行输出后都应跟一个换行符。你必须确保每行输出后都刷新缓冲区。

输出

参见上述交互协议。

数据范围

$1 \le n \le 10^5$ $1 \le k \le 2n$ 每个分数介于 $1$ 和 $10^9$ 之间 你总共最多可以进行 $100$ 次前两种类型的询问

样例

3 1
F 1
9
S 1
8
! 9

说明：芬兰的分数为 $[9, 4, 3]$，瑞典的分数为 $[8, 6, 1]$。由于 $k=1$，任务是求出整体的最高分，在此例中即为 $9$。