BallsInBoxes | Topcoder Archive

Problem Statement

There are N boxes arranged in a row. The boxes are numbered 0 through N-1 from left to right.

Cat Snuke knows that exactly K consecutive boxes contain balls. Formally, there exists some i (0 <= i <= N-K) such that the boxes i, i+1, ..., i+K-1 contain balls while all others are empty.

He wants to determine which boxes contain balls. In each turn, he can choose a box, open it and check whether the box contains a ball or not. Note that the result of each turn may affect his future decisions about which boxes to open in the next turns.

How many turns are required to determine the positions of the balls in the worst case, assuming that Snuke uses the optimal strategy?

Definition

Class:: BallsInBoxes
Method:: maxTurns
Parameters:: long, long
Returns:: long
Method signature:: long maxTurns(long N, long K)
(be sure your method is public)

Constraints

N will be between 1 and 10^18, inclusive.
K will be between 1 and N, inculsive.

Examples

```
10
```
```
10
```
```
Returns: 0
```
Snuke knows that all boxes contain balls, so he doesn't need to open any boxes.
```
100
```
```
1
```
```
Returns: 99
```
In the worst case, if he opens 98 boxes and none of them contains the only ball, he can't determine which box contains the ball.
```
1000
```
```
999
```
```
Returns: 1
```
There are two possibilities: Boxes 0, 1, ..., 998 contain balls. Boxes 1, 2, ..., 999 contain balls. He can determine the positions of the balls if he opens box 0.
```
10
```
```
5
```
```
Returns: 3
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.