UnsafeBuilding | Topcoder Archive

Problem Statement

You have recently constructed a tall rectangular building. Each of the 4 corners of the building was constructed by attaching N long beams, end to end. Unfortunately, the beams used were not quite all the same length. After construction it was discovered that each beam had a 50% chance of being one millimeter longer than it should have been. It's too late to easily figure out which beams were longer and which beams were the correct length. However, simulations show that the integrity of the building is greatly compromised if, after placing the bottom k beams on each corner, for some k <= N, the difference between the height of any two corners was M millimeters or greater. Given that each beam had a 50% chance (independently) of being one millimeter too long, return the probability that the integrity of the building was compromised by the length difference.

Definition

Class:: UnsafeBuilding
Method:: probability
Parameters:: int, int
Returns:: double
Method signature:: double probability(int N, int M)
(be sure your method is public)

Notes

Your return must have error less than 1E-9.

Constraints

N will be between 1 and 100, inclusive.
M will be between 1 and 40, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 0.875
```
There is only one beam at each corner, but any difference between beam lengths compromises the building. Thus, the beams must all be the correct length, or all be one millimeter too long for the building to be safe. Each of these two events happens 1/16 of the time, so the building is safe 1/8 of the time, and unsafe 7/8 of the time.
```
1
```
```
2
```
```
Returns: 0.0
```
```
2
```
```
2
```
```
Returns: 0.4296875
```
```
3
```
```
2
```
```
Returns: 0.671875
```

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.