Tasters and the Spoiled Cask

Hard

A cellar holds casks casks, and exactly one of them contains spoiled wine. Volunteer tasters help find it. Testing happens in rounds. At the start of a round, each taster may sip from any set of casks (several people may sip from the same cask), and this takes no time. After react_minutes minutes everyone who tasted the spoiled wine feels sick and drops out; the others carry on. A new round can only start after that. You have total_minutes minutes in total. Return the smallest number of tasters that guarantees you can identify the spoiled cask in the time available.

Example 1

casks=8, react_minutes=10, total_minutes=10 → 3

There is time for a single round, and each taster gives a yes/no answer. Three tasters cover 2³ = 8 casks: each cask gets its own drank/didn't-drink pattern.

Example 2

casks=9, react_minutes=15, total_minutes=30 → 2

There are two rounds, so each taster has three outcomes: sick after round one, after round two, or never. Two tasters cover 3² = 9 casks.

Example 3

casks=1, react_minutes=5, total_minutes=20 → 0

Constraints

1 ≤ casks ≤ 1000
1 ≤ react_minutes ≤ total_minutes ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming Combinatorics

Similar problems

Radio Show Without Quick Repeats Hard Parcel Run Orders Hard A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard K-th Route in Alphabetical Order Hard

Input

casks=8, react_minutes=10, total_minutes=10

Expected

Run checks the first 3 tests in your browser. Submit checks all 93 tests on the server, hidden ones included.