1291 : 较轻的小球

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

5 1
2
5 2
1
0

5
3

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;
}

Source

Author

CSGrandeur