A14483 | $Easy Scheduling$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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. You shall calculate the smallest number of time moments the system needs to perform all the tasks.

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.

For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks.

输入 #1

输出 #1

7
4
173

C++ 编辑器

输入

输出