首页 > 代码库 > 发 零 食

发 零 食

发 零 食

(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

1

6

4 2

3 4

10 1

2 2

8 128

dropping.out

1 : 12

2 : 7

3 : 512

4 : 3

5 : 255

Hint

测试点编号

1、2

T<=1 D<=10

3、4、5

T<=20 D<=25

6、7、8、9

T<=700 D<=30

10 T<=1 D<=1

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

 

 1 #include <cstdio> 2 #include<cstring> 3 using namespace std; 4  5 int t,a, cnt, I, d; 6 int num[100000]; 7 void mul() 8 { 9     int x=0;10     for(int i=1;i<=num[0];i++)11      {12          num[i]=num[i]*2+x;13          x=num[i]/10;14          num[i]%=10;15      }16     if(x) num[++num[0]]=x;17 }18 void add()19 {20     int x=0;21     num[1]+=1;22     int i=1;23     while(num[i]>10)24     {25         num[i+1]+=1;26         i++;27     }28     if(num[num[0]+1]) num[0]++; 29 }30 int main()31 {32     freopen("dropping.in","r",stdin);33     freopen("dropping.out","w",stdout);34     scanf("%d",&a);35     scanf("%d",&t);36     for(int k=1;k<=t;k++)37     {38         scanf("%d%d",&d,&I);39         memset(num,0,sizeof(num));40         cnt =  1;41         num[0] =num[1]=1;42         while (cnt < d)43         {44             if (I % 2)45             {46                 I =  (I + 1) / 2;47                 mul();48             }49             else50             {51                 I /= 2;52                 mul();53                 add();54             }55             cnt++;56         }57         printf("%d : ",k);58         for(int i=num[0];i;i--) printf("%d",num[i]);59         printf("\n\n");60     }61     return 0;62 }

 

发 零 食