#Cg5. 天平称金币

天平称金币

天平称金币

题目描述

这是一道交互题。

有 NN 枚外表完全相同的金币,编号为 1∼N1 \sim N。金币总数 NN 保证是 3 的正整数次幂(即 N=3kN = 3^k)。 已知这批金币中恰好藏有 1 枚假币,假币的重量比真币略重一点;所有真币的重量都严格相同。

你有一架高精度的天平秤。每次称重,你可以在天平的左右两个托盘上各放入数量相同且互不重叠的一组连续金币 [a,b][a, b] 与 [c,d][c, d](要求两边硬币数相同,即 b−a=d−cb - a = d - c)。天平会反馈称重结果:

  • >:左盘比右盘重(说明假币在左盘 [a,b][a, b] 中);
  • <:右盘比左盘重(说明假币在右盘 [c,d][c, d] 中);
  • =:两盘平衡(说明假币不在天平上的这两组中)。

你最多只能称重 k=log⁡3Nk = \log_3 N 次。请找出那枚较重的假币的编号!

交互方式

交互开始时,你的程序先从标准输入读入两个整数 NN 和 kk。

随后发起称重询问,向标准输出打印一行: ? a b c d 其中要求 1≤a≤b<c≤d≤N1 \le a \le b < c \le d \le N 且 b−a=d−cb - a = d - c。输出后必须刷新输出缓冲区(例如在 C++ 中使用 std::endl)。 随后从标准输入读入一个字符(>、< 或 =)。

当你确定假币编号 xx 时,向标准输出打印一行: ! x 刷新缓冲区并正常结束程序。

样例交互过程

交互器输出 选手程序输出 说明
27 3 共 27 枚金币,最多称重 3 次
? 1 9 10 18 称量第 1~9 枚 与 第 10~18 枚
< 右边重,说明假币在 [10,18][10, 18] 中
? 10 12 13 15 称量第 10~12 枚 与 第 13~15 枚
= 平衡,说明假币在剩下的 [16,18][16, 18] 中
? 16 16 17 17 称量第 16 枚 与 第 17 枚
< 右边重,说明假币是第 17 枚
! 17 确定答案并报告

数据规模与提示

对于 100%100\% 的数据,满足 1≤k≤101 \le k \le 10,N=3kN = 3^k(即 3≤N≤590493 \le N \le 59049)。最多允许称重 kk 次。