New Year's Eve Wine Pyramid
Time limit5sMemory limit512 MB
Wine poured into the top glass of a pyramid of glasses overflows in equal thirds to the level below, and each query asks how much one glass holds.
- Level
Medium4 of 10
- Topics
- Simulation
- Solved
- No attempts yet
Problem
Wine glasses are stacked in a pyramid at a new year's party. The top level holds one glass, the level below it holds three, the next holds six, and the one after that holds ten. The picture below shows the shape.

A glass is identified by two numbers, and . is the level the glass sits on and is the number of the glass inside that level. Glasses on a level are numbered like this:
Level 1:
1
Level 2:
1
2 3
Level 3:
1
2 3
4 5 6
Level 4:
1
2 3
4 5 6
7 8 9 10
Level is a triangle of rows holding 1 glass up to glasses, so it has glasses. The glass in position of row has number .
Each glass holds 250ml of wine. The bartender pours wine into the top glass (, ) from bottles of 750ml each.
Once a glass is full, the wine that no longer fits overflows in equal parts into the three glasses of the next level that touch it, and nothing is spilled outside. Wine never overflows sideways into a glass on the same level, and it never falls straight past the next level. Wine that overflows from the glass in position of row on level reaches position of row , position of row , and position of row on level . For example, when the glass with and overflows, the wine reaches the glasses with and equal to 2, 4 and 5.
After the bartender has poured all bottles, find how much wine in ml the glass with number on level holds.
Input
The first line has the number of test cases, . test cases follow. Each test case is three integers , and . is the number of bottles the bartender pours, is the level the glass sits on and is the number of the glass inside that level.
Output
For each test case print one line in the form "Case #x: y", where is the test case number starting from 1 and is the amount of wine in ml in that glass. Round to seven decimal places and print all seven digits, including trailing zeros.