Gym - 100952B

B. New Job

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

310 107 25 3

output

443

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.

模拟一下,一直复制cnt*2,当cnt>m时,一直复制m。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8
 9 int main(){
10     int t;
11     ll n,m;
12     //cout << (4.1) << endl;
13     cin>>t;
14     while(t--){
15         cin>>n>>m;
16         ll ans = 0;
17         ll cnt = 1,sum = 0;
18         while(cnt <= m && sum < n){
19             ans++;
20             sum = sum + cnt;
21             cnt = cnt*2;
22         }
23         if(sum >= n){
24             cout << ans << endl;
25             continue;
26         }
27         if(cnt > m){
28             cnt = m;
29             ll sh = n-sum;
30             ans = ans + sh/cnt;
31             if(sh%cnt!=0)ans++;
32             cout << ans << endl;
33         }
34     }
35     return 0;
36 }
时间: 07-16

Gym - 100952B的相关文章

CodeForces Gym 100935D Enormous Carpet 快速幂取模

Enormous Carpet Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Gym 100935D Description standard input/outputStatements Ameer is an upcoming and pretty talented problem solver who loves to solve problems using computers.

B - Average Gym - 101161B 组合数学

http://codeforces.com/gym/101161/attachments 今天被卡常了,其实是自己对组合数技巧研究的不够. 如果是n, m <= 1e5的,然后取模是质数,那么可以用费马小定理. 如果n, m都比较小,那么其实是直接杨辉三角.不用逆元那些. 这题的思路是,枚举每一一个ave,然后总和就是n * ave 相当于方程  x1 + x2 + .... + xn = n * ave中,在0 <= x[i] <= full的情况下,不同解的个数中,使得x[i] ==

Codeforces Gym 100269 Dwarf Tower (最短路)

题目连接: http://codeforces.com/gym/100269/attachments Description Little Vasya is playing a new game named "Dwarf Tower". In this game there are n different items,which you can put on your dwarf character. Items are numbered from 1 to n. Vasya want

CodeForces Gym 101063C 二进制压缩

http://codeforces.com/gym/101063/problem/C 给n个人,m样物品,每个人可以从物品中选择几样.两人选择物品的交集元素个数比上并集元素个数如果大于某个比例即可将两人配对.求配对数. n的范围是1e5,直接比较所有人的选择会TLE,应该将所有选择物品的情况用二进制压缩,m最大是10,情况数目小于2048,可以接受.注意配对总数范围应为long long. #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> i

Gym 101246H ``North-East&#39;&#39;(LIS)

http://codeforces.com/gym/101246/problem/H 题意: 给出n个点的坐标,现在有一个乐队,他可以从任一点出发,但是只能往右上方走(包括右方和上方),要经过尽量多的点.输出它可能经过的点和一定会经过的点. 思路: 分析一下第一个案例,在坐标图上画出来,可以发现,他最多可以经过4个点,有两种方法可以走. 观察一下,就可以发现这道题目就是要我们求一个LIS. 首先,对输入数据排一下顺序,x小的排前,相等时则将y大的优先排前面. 用二分法求LIS,这样在d数组中就可

Gym 100712I Bahosain and Digits(开关翻转问题)

http://codeforces.com/gym/100712/attachments 题意: 给出一串数字,每次选择连续的k个数字加上任意数(超过10就取余),最后要使得所有数字都相等,求最大的k. 思路: 开关翻转问题. 算法具体可以参考<挑战程序竞赛>常用技巧篇. 这道题目就是在枚举k的同时再枚举一下最后要转换成的数字即可. 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring>

很好的脑洞题:dfs+暴力 Gym - 101128A Promotions

http://codeforces.com/gym/101128 题目大意:给你一个a,b,e,p.有e个点,p条有向边,每条边为(x,y),表示x->y,每次我们都取出一个入度为0的,并且一次性取出来的个数为a(或b).当然,取出来的种类可能有很多种(即一个集合),问,这个集合中有多少个数字是相同的. 第一个输出集合长度为a的,第二个输出集合长度为b的,第三个输出无论如何都无法被取出的个数. 思路:建立正向图和反向图. 定义pair<int, int> interval[i] 表示第i

【树状数组】Gym - 101147J - Whistle&#39;s New Car

题意就是对每个点i,统计在其子树内(不含自身),且depj-depi<=xj的点有多少个. 把点分别按照dep-x和dep进行排序,离线处理, 每次把dep-x小于等于当前dep值的点插入树状数组,就变成了询问dfs序在一个区间内的点有多少个,可以用树状数组轻松解决. #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int f,C; void R(int &am

SYSU-7, Gym 100273J, trie+hash

cnm毛子的题是正宗内家拳法啊orz(捶地),拼的就是智商,这题我们队想了老半天后缀自动机,掏出各种黑科技无果 题目大意:构建一个自动机可以表达给定的n个串,询问最小的自动机节点树为多少. 解:最裸的自动机其实就是一棵trie,那么我们考虑优化这棵trie,考虑拓扑排序倒过来做,可以发现其实如果两个节点如果他们指向的节点状态完全一致,那么这两个节点是等价的,所以我们不断合并这些节点即可.但是拓扑可能会慢,而且貌似会退化n方(没细想),但一般地,我们用dfs出栈序去做这个hash去重即可. cnm