HouseOfCards
SRM 827 · 2022-04-04 · by misof
Problem Statement
A house of cards is a pyramid-shaped construction made entirely of cards.
The main unit (which we will call a block) consists of two cards leaning against each other, roughly like this:
/\
/ \
The bottom floor of the pyramid consists of N blocks standing next to each other.
As long as you have more than one block, you can build an additional floor. The new floor is built as follows:
- Add a ceiling: For each pair of adjacent blocks on the current top floor, place a horizontal card that will cover both their tops.
- Add the new floor: For each horizontal card you just placed, put a new block onto that card.
Clearly, the new floor will have one fewer block than the previous one.
The pyramid is complete once you build a floor that consists of a single block.
Given the number N of blocks that form the bottom floor, compute and return the total number of cards needed to build the pyramid.
Notes
- Watch out for integer overflow: the result may not fit into a 32-bit variable.
Constraints
- N will be between 1 and 100,000, inclusive.
1 Returns: 2
You take two cards, build a single block, and that's it.
2 Returns: 7
You need four cards to build two blocks, then one card to put on their tops horizontally, and then two more cards to build one block on top of that card. The resulting house of cards looks roughly as follows: /\ / \ ------ /\ /\ / \/ \
4 Returns: 26
We start by placing four blocks next to each other to form the bottom floor. Then we place three cards horizontally on top of them and we are ready to build the next floor. And so on, until the top. An ASCII art of the full house follows. ('=' denotes places where two adjacent horizontal cards partially overlap.) /\ / \ ------ /\ /\ / \/ \ ----==---- /\ /\ /\ / \/ \/ \ ----==--==---- /\ /\ /\ /\ / \/ \/ \/ \
3 Returns: 15
7 Returns: 77
Submissions are judged against all 14 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HouseOfCards with a public method long long count(int N) · 14 test cases · 2 s / 256 MB per case