Gym 100952B&&2015 HIAST Collegiate Programming Contest B. New Job【模拟】

B. New Job

time limit per test:1 second

memory limit per test:64 megabytes

input:standard input

output:standard output

This is the first day for you at your new job and your boss asks you to copy some files from one computer to other computers in an informatics laboratory. He wants you to finish this task as fast as possible. You can copy the files from one computer to another using only one Ethernet cable. Bear in mind that any File-copying process takes one hour, and you can do more than one copying process at a time as long as you have enough cables. But you can connect any computer to one computer only at the same time. At the beginning, the files are on one computer (other than the computers you want to copy them to) and you want to copy files to all computers using a limited number of cables.

Input

First line of the input file contains an integer T (1  ≤  T  ≤  100) which denotes number of test cases. Each line in the next T lines represents one test case and contains two integers N, M.

N is the number of computers you want to copy files to them (1  ≤  N  ≤  1,000,000,000). While M is the number of cables you can use in the copying process (1  ≤  M  ≤  1,000,000,000).

Output

For each test case, print one line contains one integer referring to the minimum hours you need to finish copying process to all computers.

Examples

Input

3
10 10
7 2
5 3

Output

4
4
3

Note

In the first test case there are 10 computer and 10 cables. The answer is 4 because in the first hour you can copy files only to 1 computer, while in the second hour you can copy files to 2 computers. In the third hour you can copy files to 4 computers and you need the fourth hour to copy files to the remaining 3 computers.

题目链接:http://codeforces.com/gym/100952/problem/B

题意:将一个文件复制到n台电脑上,但是只有m条网线,每台电脑一次只能连接一根网线,输出多少时间可以完成复制!

分析:模拟一下就好了! 下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline int read()
 5 {
 6     int x=0,f=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9')
 9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(int x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29     {
30         write(x/10);
31     }
32     putchar(x%10+'0');
33 }
34 inline ll gcd(ll x,ll p,ll mod)
35 {
36     ll cnt=1;
37     for(;p;p>>=1,x=x*x%mod)
38     {
39         if(p&1)
40             cnt=cnt*x%mod;
41     }
42     return cnt;
43 }
44 ll n,m;
45 int main()
46 {
47     int t;
48     t=read();
49     while(t--)
50     {
51         ll ans=0;
52         n=read();
53         m=read();
54         ll tim=1;
55         while(1)
56         {
57             if(tim>=m)
58             {
59                 tim=m;
60                 ans+=(n/tim);
61                 if(n%tim)
62                    ans++;
63                 break;
64             }
65             ans++;
66             n-=tim;
67             tim=tim*2;
68             if(n<=0)
69                break;
70         }
71         cout<<ans<<endl;
72     }
73     return 0;
74 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

Go指南练习_Stringer

1292
来自专栏SDNLAB

OFTest(一):如何忽略一些字段在端口poll报文

1 前言 ✔ 关于OFTest的介绍,请戳这里(https://github.com/floodlight/oftest) ✔ 总的来说,就是用python写的...

3709
来自专栏数据结构与算法

10:判决素数个数

10:判决素数个数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个整数X和Y,输出两者之间的素数个数(包括X和Y...

3876
来自专栏前端进阶之路

带你彻底弄懂Event Loop前言正文总结

我在学习浏览器和NodeJS的Event Loop时看了大量的文章,那些文章都写的很好,但是往往是每篇文章有那么几个关键的点,很多篇文章凑在一起综合来看,才可以...

1264
来自专栏拂晓风起

中文URL编码

1885
来自专栏java一日一条

Java并发编程之原子操作类

当更新一个变量的时候,多出现数据争用的时候可能出现所意想不到的情况。这时的一般策略是使用synchronized解决,因为synchronized能够保证多个线...

851
来自专栏Golang语言社区

网络后台开发面试题

1.C++模板的作用。 将算法与具体对象分离,与类型无关,通用,节省精力 2.socket编程,如果client断电了,服务器如何快速知道??? 有以下几个...

6538
来自专栏向治洪

访问者模式

概念 访问者模式:表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素类的前提下定义作用于这些元素的新操作。 访问者模式的目的是封装一些施加于...

2255
来自专栏程序员的知识天地

Python实现堆栈

堆栈是一个后进先出的数据结构,其工作方式就像一堆汽车排队进去一个死胡同里面,最先进去的一定是最后出来。

1512
来自专栏大内老A

采用一个自创的"验证框架"实现对数据实体的验证[设计篇]

没有想到自己头脑发热写了一个简陋版本的所谓“验证框架”能够得到众多网友的推荐。个人觉得这个验证框架有两个主要的特点是:提供CompositeValidator使...

2088

扫码关注云+社区

领取腾讯云代金券