Compute expected days until no whole pills

Q: Compute expected days until no whole pills

This is a Coding & Algorithms interview question from Qube for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

A bottle initially contains H half-pills and W whole pills.

Each day:

You randomly select one pill uniformly from the bottle.
If it is a half-pill , you consume it entirely (it is removed).
If it is a whole pill , you consume half and put the remaining half back into the bottle. (So selecting a whole pill decreases the number of whole pills by 1 and increases the number of half-pills by 1.)

You always consume exactly half a pill per day.

Task: Compute the expected number of days until the bottle contains no whole pills (i.e., only half-pills remain).

Input

Two integers H and W .

Output

A floating-point number: the expected number of days until W = 0 .

Example instance

H = 25 , W = 25 .

Constraints (for your implementation)

You may assume 0 ≤ H, W ≤ 200 (or similar), and you should output the expectation with reasonable precision (e.g., 1e-6 ).

Compute expected days until no whole pills

Input

Output

Example instance

Constraints (for your implementation)

Comments (0)