1291 : 较轻的小球
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 128 兆MB
- 提交次数Submitted
- 767 次Times
- 通过次数Solved
- 220 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
有个古老的问题,n个本应该重量相同的小球,但有1个次品比其它的都轻,要用一个天平把它尽快找出来。
一个直观的方法是每次把所有小球尽可能平均地放在天平两边,保留轻的那一边的小球再次平均放在两边,直到剩下最后的小球。
假设小球依次编号 1~n,对于每次保留下来 x
个小球,下一次按编号顺序把前 \(\lfloor x / 2
\rfloor\) 个小球放天平左边,接下来相同个数放右边。
如果是奇数个小球,则最后一个小球不放上天平,如果此时天平平衡,则较轻的小球就是它了,否则继续处理。
输入格式Input
每组数据第一行为两个正整数 \(2 \leq n \leq 1000\) 与 \(1 \leq m \leq \lceil log(n) \rceil\),表示 \(n\) 个小球和 \(m\) 次称量。
接下来 \(m\) 行正整数,\(0\)表示左边轻,\(1\)表示右边轻,\(2\)表示天平平衡。
数据保证恰好能够找出较轻的小球,不会有冗余的输入。
输出格式Output
根据称量情况,输出次品小球的编号。
样例Sample
提示Hint
对于前一组数据,5个小球,1、2在左,3、4在右,5没有放上天平,结果为“2”平衡,则较轻的为5号。
第二组数据,第一次称量为“1”右边轻,则将3、4号小球放天平,第二次称量为“0”左边轻,则较轻的为3号。
参考代码框架:
// 较轻的小球
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int lrFlag;
int Check(int l, int r)
{
// TODO: 判断左闭右开区间[l, r)中较轻小球的编号并返回
// 1. 处理递归终点,区间只有1个小球的情况
// 2. 将区间分为 “前⌊x/2⌋个” 、“接下来的前⌊x/2⌋个”、“如果是奇数个则剩下有1个”
// 3. 读入对这两部分称量结果
// 4. 根据称量结果,决定如何处理,比如对一部分继续递归,还是已得到答案
}
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
printf("%d\n", Check(1, n + 1));
return 0;
}出题Author
CSGrandeur
来源Source
算法竞赛入门-函数-递归
题目到此结束End of problem