发 零 食

(dropping.cpp/c/pas)

Description

HKD 看学弟学妹们学习辛苦，决定给发零食吃

HKD 是土豪，所以他决定买零食的时候，从 1 块钱的开始买，然后买 2 块钱的，然后 3 块钱

的，……，直至 D 块钱的。而且 k 块钱的零食买 2^(k-1)个。

但 HKD 从来不吃零食，所以他不知道他买的零食是否好吃。

于是他把所有零食编号，怎么编呢？

对于价钱为 k 的零食，从 1 开始编，然后 2,3，编到 2^(k-1)

例：1 块钱的：1

2 块钱的：1 2

3 块钱的：1 2 3 4

学编程的基本功是搜索嘛

为了考验学弟学妹们的搜索能力

HKD 把所有零食掺杂在了一起，送到学弟学妹们的面前（送货上门，真好）

他规定：

1、只能排队一个一个开始搜

2、所有人最终只能吃 1 个零食

3、所有人只能吃最贵的零食

4、 所有人搜索零食的时候， 只能从 1 块钱的开始搜， 然后搜 2 块钱的， 然后搜 3 块钱的……，

直到最贵的

5、初始时认为所有零食都是好吃的

6、 为了增加难度， HKD 制定了新规定： 若一个人搜到的第 i 块钱的编号为 j 的零食是好吃的，

那么他就把这个零食更改为不好吃，然后去搜第 i+1 块钱的编号为 j*2-1 的零食。若一个人

搜到的第 i 块钱的编号为 j 的零食是不好吃的，那么他就把这个零食更改为好吃，然后去搜

第 i+1 块钱的编号为 j*2 的零食

注：若 n 个人都最后搜到了同一个零食，那么他们就分享一个吧

然而不知道为啥，HKD 想知道最后一个人吃的是编号为几的零食

那就麻烦最后一个人告诉他吧

注：若其中有一个人无法搜到最贵的零食，就告诉他-1

Input

第一行输入测试点编号

下一行输入 T，表示有 T 组数据

接下来 T 行，每行输入 2 个数输入 D 和学弟学妹的人数 M

Output

对于每组测试数据

输出一行 k : ans，表示第 k 组数据的答案为 ans

冒号与每个数字之间空 1 格

每 2 组数据之间空一行

Example

dropping.in dropping.out

1

6

4 2

3 4

10 1

2 2

8 128

1 : 12

2 : 7

3 : 512

4 : 3

5 : 255

Hint

测试点编号

T D

1、2

<=1 <=10

3、4、5

<=20 <=25

6、7、8、9

<=700 <=30

10 <=1 <=1

学弟学妹人数 M <2^31 且不超过 D 块钱的零食个数。

思路： 我只想说

          这道题百分之三十的数据是原题

          还被我加在了codevs上

          但是，，，

          这道题搜索居然会超时，，，，，，，，，，，，，，，，，，

          So另一种思路：

       同一个节点，在两个不同的小球经过时，会出现不同的情况，一种向左走，一种向右走；

当该节点是奇数的话，说明他一定是*2+1得来的，ans需要*2；；如果是偶数的话，说明一定是*2得来的，ans需要*2+1；

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 int main(void)
 6 {
 7     //freopen("dropping.in","r",stdin);
 8 //    freopen("dropping.out","w",stdout);
 9     int meiyong;
10     cin>>meiyong;
11     int t;
12     cin>>t;
13     for(int k=1;k<=t;k++)
14     {
15         int n,I,ans=1;
16         scanf("%d%d",&n,&I);
17         //int max=1<<n-1;
18         int max=pow(2,n-1);
19         while (ans<max)
20         {
21             if (I%2==1) 
22             {
23                 I=I/2+1;
24                 ans=ans*2;
25             } 
26             else 
27             {
28                 I=I/2;
29                 ans=ans*2+1;
30             }
31         }
32         printf("%d : %d\n\n",k,ans);
33     }
34     return 0;
35 }