codeforces415D. Glad to see you!(交互)
2018-08-02 05:43:43来源:博客园 阅读 ()
题意
交互题。
有$k$个值域为$[1, n]$的数。
请在不超过$60$次询问内找出其中的两个数。
每次询问形式为1 x y
交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$
其中$a, b$分别是使得$|x - a|,|y - b|$最小的且存在于序列中的数。
Sol
若询问$x, x + 1$的结果为“TAK”,说明在$1, x$内一定有解。
我们可以不断这样二分下去。直到找到一个解。
再在$1, x - 1$和$x +1, N$中重复以上操作,找到另一组解。
#include<iostream> using namespace std; int N, K; string Yes = "TAK"; int check(int x) { if(x + 1 > N) return 1; printf("1 %d %d\n", x, x + 1); fflush(stdout); string buf; cin >> buf; return buf == Yes ? 1 : 0; } int Query(int l, int r) { int ans = -1; while(l <= r) { int mid = l + r >> 1; if(check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> K; int a1 = Query(1, N); int a2 = Query(1, a1 - 1); int a3 = Query(a1 + 1, N); printf("2 %d %d", a1, a2 == -1 ? a3 : a2); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C-fopen,fwrite,fread,fseek,fgets,popen,access笔记 2018-12-04
- BZOJ 1941: [Sdoi2010]Hide and Seek(k-d Tree) 2018-06-27
- stream的seek方法实例 2018-06-18
- FILE文件流的中fopen、fread、fseek、fclose的使用 2018-06-17
- Seek the Name, Seek the Fame POJ - 2752 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash