← 返回题目列表

Codeforces · 809/B

B. 很高兴见到你!

中文机器翻译题面 查看原题

这是一个交互问题。在下面的输出部分中,您将看到有关刷新输出的信息。

周日,Leha 黑客将 Nura 从她居住的房子里带走,并与她一起去了 Vičkopolis 最豪华的餐厅之一。抵达后,他们把车停在餐厅附近的一个巨大停车场,然后匆匆进了大楼。

餐厅里,一位彬彬有礼的服务员立刻把菜单拿给了Leha和Noora,菜单上有n道菜。有趣的是,菜单中的所有菜肴都用1到n的整数进行编号。想了想,女孩点了菜单上的 k 种不同的菜肴。为了打发厨师准备菜肴的等待时间,女孩邀请黑客玩一个游戏,以帮助他们更好地了解彼此。

游戏本身非常简单:Noora 希望 Leha 猜出所有点的菜中的任意两道菜。同时,她只准备回答一类问题。 Leha 可以说出两个数字 x 和 y (1 ≤ x, y ≤ n)。之后Noora为数字x选择了一些菜肴a,这样,首先,a是Noora订购的菜肴之一(x可以等于a),其次,值$$|x-a|$$是可能的最小值。按照同样的规则,女孩为 y 选择菜 b。之后,Noora 对 Leha 说“TAK”,如果 $$|x-a| \leq |y-b|$$,否则为 «NIE»。不过,餐厅准备得很快,所以 Leha 有足够的时间问不超过 60 个问题。之后,他应该说出努拉点的任意两道菜的编号。

帮助Leha解决这个问题!

输入

单行输入中有两个数字n和k(2≤k≤n≤105),分别表示菜单中的菜品数量和Noora点的菜品数量。

互动

在帮助 Leha 的同时,您向 Noora 询问的次数不得超过 60 次。每个查询应打印在其自己的行中,并具有形式 1 x y (1 ≤ x, y ≤ n)。您必须打印行尾字符并刷新输出。刷新后,您应该从输入中读取此查询的答案。

在每个查询之后,陪审团的程序将根据女孩的答案在输入流中打印一行“TAK”或“NIE”(不带引号)。

要刷新,您可以使用(在打印整数和行尾之后):

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

黑客攻击

对于黑客攻击,你应该在第一行写下数字 n 和 k (2 ≤ k ≤ n ≤ 105),为了描述 Noora 订购的菜肴,k 个不同的整数 a1, a2, ..., ak (1 ≤ ai ≤ n),按升序写在第二行。当然,您想要破解的解决方案将无法读取所点菜肴的数量。

输出

如果你想提供答案,如果你认为菜品 x 和 y 是 Noora 点的菜品,请输出 2 x y (1 ≤ x, y ≤ n, x ≠ y) 形式的字符串。之后,刷新输出并终止程序。

示例

输入 #1

3 2
NIE
TAK
NIE
TAK
TAK
TAK

输出 #1

1 1 2
1 2 1
1 1 3
1 3 1
1 2 3
1 3 2
2 2 3

注意

样品中有三道菜。努拉点了 2 号和 3 号菜肴,莱哈应该猜到了。如果 Noora 收到对第一道菜 (x = 1) 的请求,那么她会选择第二道菜 (a = 2) 作为价值 $$|x-a|$$ 最小值的菜。对于第二个 (x = 2) 和第三个 (x = 3) 菜肴本身将是最佳的,因为在这种情况下 $$| x - 一个 | = 0$$。

让 Leha 向 Noora 询问接下来的几道菜:

- x = 1, y = 2, 那么他会收到 «NIE» 答案,因为 |1 - 2| > |2 - 2|
- x = 2, y = 1, 那么他会收到 «TAK» 答案,因为 |2 - 2| ≤ |1 - 2|
- x = 1, y = 3, 那么他会收到 «NIE» 答案,因为 |1 - 2| > |3 - 3|
- x = 3, y = 1, 那么他会收到 «TAK» 答案,因为 |3 - 3| ≤ |1 - 2|
- x = 2, y = 3, 那么他会收到 «TAK» 答案,因为 |2 - 2| ≤ |3 - 3|
- x = 3, y = 2, 那么他会收到 «TAK» 答案,因为 |3 - 3| ≤ |2 - 2|

根据现有信息,可以说Nura点了2号和3号菜肴。