codeforces-scrape

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

1578E.md (2038B)


      1 Source: https://codeforces.com/problemset/problem/1578/E
      2 
      3 E. Easy Scheduling
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Eonathan Eostar decided to learn the magic of multiprocessor systems. He has a full binary tree of tasks with height $h$. In the beginning, there is only one ready task in the tree — the task in the root. At each moment of time, $p$ processes choose at most $p$ ready tasks and perform them. After that, tasks whose parents were performed become ready for the next moment of time. Once the task becomes ready, it stays ready until it is performed.
     22 
     23 You shall calculate the smallest number of time moments the system needs to perform all the tasks.
     24 
     25 Input
     26 
     27 The first line of the input contains the number of tests $t$ ($1 \leq t \leq 5\cdot 10^5$). Each of the next $t$ lines contains the description of a test. A test is described by two integers $h$ ($1 \leq h \leq 50$) and $p$ ($1 \leq p \leq 10^4$) — the height of the full binary tree and the number of processes. It is guaranteed that all the tests are different.
     28 
     29 Output
     30 
     31 For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks.
     32 
     33 Example
     34 
     35 Input
     36 
     37 ```
     38 3
     39 3 1
     40 3 2
     41 10 6
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 7
     48 4
     49 173
     50 ```
     51 
     52 Note
     53 
     54 Let us consider the second test from the sample input. There is a full binary tree of height $3$ and there are two processes. At the first moment of time, there is only one ready task, $1$, and $p_1$ performs it. At the second moment of time, there are two ready tasks, $2$ and $3$, and the processes perform them. At the third moment of time, there are four ready tasks, $4$, $5$, $6$, and $7$, and $p_1$ performs $6$ and $p_2$ performs $5$. At the fourth moment of time, there are two ready tasks, $4$ and $7$, and the processes perform them. Thus, the system spends $4$ moments of time to perform all the tasks.
     55 
     56 ![](https://espresso.codeforces.com/09dd6de2e47829f6e64e4758b577d8a233e85246.png)