Problem C
Champagne Overflow
A champagne pyramid is an arrangement of coupes (shallow glasses) used for festive occasions such as wedding receptions or New Year’s celebrations. The construction is based on the fact that a coupe can be placed on top of four others coupes, arranged in a symmetric fashion such that liquid overflowing from the top coupe is distributed equally among the four coupes below it.
Below is the champagne pyramid of height $3$ after champagne corresponding to $5$ coupes has been poured into the topmost coupe. It has overflowed and exactly filled all coupes on the middle level as well.
![\includegraphics[width=.3\textwidth ]{img/sample3.jpg}](/problems/wcfd22.champagneoverflow/file/statement/en/img-0002.jpg)
Liquid overflowing from the bottom-most coupes – those on the table – is wasted. The construction can be iterated, leading to splendid towers of dizzying height. As of $2022$, the highest documented champagne tower consisted of more than fifty-thousand coupes.
In an ideal world, where every overflowing coupe distributes its liquid equally among its four supporting coupes, how much champagne is wasted when filling a champagne pyramid of given height from the topmost coupe?
Input
The height of the pyramid as a single integer $h$ with $1\leq h \leq 55$ (measured in coupe heights).
Output
A single integer: The amount of champagne (measured in coupes) that is wasted when filling all coupes by pouring champagne only into the topmost coupe.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 |
7 |
