codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1606B.md (3000B)


      1 Source: https://codeforces.com/problemset/problem/1606/B
      2 
      3 B. Update Files
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Berland State University has received a new update for the operating system. Initially it is installed only on the $1$-st computer.
     22 
     23 Update files should be copied to all $n$ computers. The computers are not connected to the internet, so the only way to transfer update files from one computer to another is to copy them using a patch cable (a cable connecting two computers directly). Only one patch cable can be connected to a computer at a time. Thus, from any computer where the update files are installed, they can be copied to some other computer in exactly one hour.
     24 
     25 Your task is to find the minimum number of hours required to copy the update files to all $n$ computers if there are only $k$ patch cables in Berland State University.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.
     30 
     31 Each test case consists of a single line that contains two integers $n$ and $k$ ($1 \le k \le n \le 10^{18}$) — the number of computers and the number of patch cables.
     32 
     33 Output
     34 
     35 For each test case print one integer — the minimum number of hours required to copy the update files to all $n$ computers.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 4
     43 8 3
     44 6 6
     45 7 1
     46 1 1
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 4
     53 3
     54 6
     55 0
     56 ```
     57 
     58 Note
     59 
     60 Let's consider the test cases of the example:
     61 
     62 * $n=8$, $k=3$:
     63   1. during the first hour, we copy the update files from the computer $1$ to the computer $2$;
     64   2. during the second hour, we copy the update files from the computer $1$ to the computer $3$, and from the computer $2$ to the computer $4$;
     65   3. during the third hour, we copy the update files from the computer $1$ to the computer $5$, from the computer $2$ to the computer $6$, and from the computer $3$ to the computer $7$;
     66   4. during the fourth hour, we copy the update files from the computer $2$ to the computer $8$.
     67 * $n=6$, $k=6$:
     68   1. during the first hour, we copy the update files from the computer $1$ to the computer $2$;
     69   2. during the second hour, we copy the update files from the computer $1$ to the computer $3$, and from the computer $2$ to the computer $4$;
     70   3. during the third hour, we copy the update files from the computer $1$ to the computer $5$, and from the computer $2$ to the computer $6$.
     71 * $n=7$, $k=1$:
     72   1. during the first hour, we copy the update files from the computer $1$ to the computer $2$;
     73   2. during the second hour, we copy the update files from the computer $1$ to the computer $3$;
     74   3. during the third hour, we copy the update files from the computer $1$ to the computer $4$;
     75   4. during the fourth hour, we copy the update files from the computer $4$ to the computer $5$;
     76   5. during the fifth hour, we copy the update files from the computer $4$ to the computer $6$;
     77   6. during the sixth hour, we copy the update files from the computer $3$ to the computer $7$.