Power Eggs

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.0s

Memory limit: 16M

Problem type

Benedict bought $K$ $K$ identical power eggs from Dropeggs.com, and now he wants to test them by dropping them from different floors of his building. His building has $N$ $N$ floors numbered $1$ $1$ to $N$ $N$ . $F$ $F$ is an unknown number in the range from $0$ $0$ to $N$ $N$ , inclusive. Each egg will break if dropped from floor $F+1$ $F + 1$ or above, but will not break if dropped from floor $F$ $F$ or below. Benedict can drop each egg as many times as he wants from any floor until it breaks. He wants to know the minimum number of egg drops necessary to ensure that he can determine $F$ $F$ .

For example, if there are three floors and Benedict has only one egg, then he has to first throw the egg from the first floor, then from the second floor (if the egg survived), and then from the third floor (if the egg survived). Therefore, three drops are required in the worst case.

Input Specification

The first line contains one number $T$ $T$ $(1 \le T \le 10\,000)$ $(1 \leq T \leq 10 000)$ which is the number of test cases, followed by $T$ $T$ lines. Each of the next $T$ $T$ lines contains two numbers: $N$ $N$ , the number of floors $(1 \le N \le 2\,000\,000\,007)$ $(1 \leq N \leq 2 000 000 007)$ and $K$ $K$ , the number of eggs $(1 \le K \le 32)$ $(1 \leq K \leq 32)$ .

Output Specification

For each of the $T$ $T$ lines, print the minimal number of drops required, or if it's greater than $32$ $32$ , print the word Impossible. After that many drops, Benedict gets too tired and cannot continue.

Sample Input

Copy

4
10 1
100 2
30 30
2000000000 2

Sample Output

Copy

10
14
5
Impossible

Comments

18

GreenRobot commented on May 21, 2020, 2:46 p.m.

What a great website to buy eggs off of.

1

kobortor commented on Oct. 2, 2015, 10:18 p.m.

Why does Benedict need 3 drops? Couldn't he infer that F = 3 after he drops the egg from the second floor and survive?

2

cheesecake commented on Oct. 2, 2015, 11:03 p.m.

After he drops it from the second floor and it survives, F could be either 2 or 3, since the egg survives at floor F.