cf1103 B. Game with modulo
2022/4/23 6:15:51
本文主要是介绍cf1103 B. Game with modulo,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
交互题
有个未知整数 \(a\in[1,1e9]\),每次问两个数 \(x,y\),返回 \(x\pmod a \ge y\pmod a\) 是否成立
在 60 次内猜出 \(a\)
思路:
倍增猜法,长见识了
首先我想到猜 \(x,2x\),若 $\ge $ 说明 \(a\in [1,2x]\),否则 \(a\in [1,x)\cup (2x,1e9)\)
这样每次得到的合法区间还分开的,不知道怎么处理。
既然 \([1,x)\) 这个区间没法确定,那每次都用一个 \(\le a\) 的 \(x\) 来问不就行了!
正解:
先问 \(1,2\),若返回 \(\ge\) 则说明 \(a\in [1,2]\),否则说明 \(a>2\) 并继续;
再问 \(2,4\),返回 \(\ge\) 说明 \(a\in [3,4]\),否则 \(a>4\) 并继续;
再问 \(4,8\),返回 $\ge $ 说明 \(a\in [5,8]\),否则 \(a>8\) 并继续。
以此类推,最后一定在某次询问 \(x,2x\) 后确定 \(a\in[x+1,2x]\) 。但是注意,区间 \([1,2]\) 是特殊情况,不知道怎么处理只好特判一下。
接下来怎么办?二分!
初始 \(l=x+1,r=2x\)
每次问 \(x,mid\),若 $\ge $ 则 \(a\le mid\),于是令 \(r=mid\);否则 \(a>mid\),于是令 \(l=mid+1\)
bool ask(int x, int y) { //是否>= cout << "? " << x << ' ' << y << endl; char c; cin >> c; return c == 'x'; } void ans(int x) { cout << "! " << x << endl; } signed main() { string ty; while(cin >> ty, ty != "end") { int x = 1; char res; while(!ask(x, 2*x)) x *= 2; if(x == 1) { ans(ask(0,1) ? 1 : 2); continue; } int l = x + (x > 1), r = x * 2; while(l < r) { int mid = (ll)l + r >> 1; if(ask(x, mid)) r = mid; else l = mid + 1; } ans(l); } }
这篇关于cf1103 B. Game with modulo的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享