TopCoder Statistics - Problem Statement

Problem Statement

Before you lies a tower of champagne glasses that must be filled. Each glass rests upon exactly 2 other glasses beneath it, with the exception of the lowest row, which sits on the table. An example of a 5 glass tall tower is shown below:

                             1
                           2   3
                         4   5   6
                       7   8   9   10
                    11  12  13   14   15

Each glass can hold 2 units of champagne, and if more than 2 units of champagne fall into any glass, all but 2 of the units will overflow equally into the two glasses below it. Thus, all of the champagne poured into glass 1 after the first 2 units will fall equally into glasses 2 and 3. Once 2 and 3 overflow they will each, independently, distribute the champagne into the two glasses beneath them. At that point glass 5 will be receiving champagne from both glasses 2 and 3. Glass 4 will be receiving champagne from just glass 2, and glass 6 will be receiving champagne from just glass 3.

Given the height of the tower, the number of units poured into glass 1, and the number of a particular glass, return what fraction of that glass is full. Your solution should be a reduced fraction (lowest terms) in the form "numerator/denominator" with no leading zeros in either the numerator or denominator. Full glasses are denoted by "1/1" whereas empty glasses are denoted "0/1". The glasses are numbered in the same way as above, namely left to right, top to bottom. Note, once a glass on the bottom layer is full, extra champagne will just spill onto the table.

Definition

Class:: Champagne
Method:: howMuch
Parameters:: int, int, int
Returns:: String
Method signature:: String howMuch(int height, int glass, int units)
(be sure your method is public)

Notes

Glass 1 is in the first row. The glass beneath it, on its left side, is glass 2. More generally, if glass i is in row j the glass beneath it, on its left side, if it exists, is glass i+j.

Constraints

height must be between 1 and 20 inclusive
glass must be a valid glass number given the value of height
units must be between 1 and 300 inclusive

Examples

20

210

300

Returns: "0/1"
1

1

1

Returns: "1/2"

Pouring only 1 unit will fill the first and only glass half way.
2

2

2

Returns: "0/1"

The top glass is full, but no champagne has spilled into glass 2.
2

3

3

Returns: "1/4"

The top glass is full and one unit of champagne has spilled out of it. This spilled champagne is evenly distributed between glasses 2 and 3.
3

4

7

Returns: "1/8"

Pouring 6 units causes glasses 1 through 3 to be full. The seventh unit of champagne will make its way to glasses 4 through 6.
3

5

7

Returns: "1/4"
20

204

300

Returns: "5581/131072"
20

204

299

Returns: "8663/262144"
17

84

98

Returns: "281/512"
13

38

165

Returns: "121/256"
14

69

249

Returns: "1203/4096"
11

64

166

Returns: "97/256"
20

204

298

Returns: "1541/65536"
20

203

299

Returns: "1/1"
20

204

300

Returns: "5581/131072"
20

204

299

Returns: "8663/262144"
5

9

300

Returns: "1/1"
20

204

297

Returns: "3665/262144"
20

4

300

Returns: "1/1"
20

119

221

Returns: "0/1"
13

13

13

Returns: "0/1"
3

4

7

Returns: "1/8"
4

9

16

Returns: "7/8"
1

1

3

Returns: "1/1"
20

132

167

Returns: "0/1"
1

1

5

Returns: "1/1"
1

1

2

Returns: "1/1"
20

5

300

Returns: "1/1"
20

1

50

Returns: "1/1"
4

9

7

Returns: "0/1"

Statistics

Problem Statement for "Champagne"

Problem Statement

Definition

Notes

Constraints

Examples