[HTOI-2] 猜球游戏
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
公司的年终大会上,小B 为了收买人心 举行了一个猜球游戏。
题目描述
有 个杯子编号为 ,从左到右排成一行,所有的杯子都倒着扣在桌上。其中某些杯子底下藏有一个小球,如果小A能准确地猜出哪些杯子中藏了小球,小A就能获得奖品。
黑心商家小B规定,花费 元就能知道第 个杯子到第 个杯子之间(包括两端)球的数量是奇数还是偶数。
小A希望猜出每个杯子底下是否藏着小球。但是小A带的钱不多,他希望采用最佳询问策略,请你告诉小A他最少需要花多少钱?
输入格式
第一行一个正整数 。
第 行( )有 个整数,表示 。
输出格式
输出一个整数,表示最少花费。
样例 #1
样例输入 #1
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
样例输出 #1
7
提示
对于 的数据,。
对于 的数据,,。
[Rated] HTOI Round 2 (Div.2)
- 状态
- 已结束
- 规则
- IOI
- 题目
- 4
- 开始于
- 2024-5-1 19:00
- 结束于
- 2024-5-5 20:00
- 持续时间
- 97 小时
- 主持人
- 参赛人数
- 28