BallsInBoxes
2015 TCO Parallel 2D · 2015-04-08 · by rng_58
2015 TCO Parallel 2D · 2015-04-08 · by rng_58 · Simple Math
Problem Statement
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?
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?
Constraints
- N will be between 1 and 10^18, inclusive.
- K will be between 1 and N, inculsive.
Examples
0)
10 10 Returns: 0
Snuke knows that all boxes contain balls, so he doesn't need to open any boxes.
1)
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.
2)
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.
3)
1000000000000000000 1 Returns: 999999999999999999
4)
1000000000000000000 1000000000000000000 Returns: 0
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BallsInBoxes with a public method long long maxTurns(long long N, long long K) · 116 test cases · 2 s / 256 MB per case