Hanger Hanger Hanger
Time limit0.5sMemory limit1024 MB
Using exactly M hangers, place complete binary hanger trees of height 1, 2, or 3 at N or fewer spots to maximize the total number of bottom hanging positions.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Combinatorics, Math, Greedy
- Solved
- No attempts yet
Problem
You need to tidy up your closet, but there are too many clothes and they are spilling onto the closet floor. There are spots where you can hang a hanger, and you have hangers. Then you realize something remarkable: when you have more hangers than the closet can hold, hanging hangers on a hanger lets you hang more clothes!

Instead of hanging clothes on a hanger, you can hang hangers on both sides of it to hold more clothes, but to keep the hanger balanced you must build a complete binary hanger where the total number of hangers on both sides is the same. Naturally, you can hang clothes only on the bottommost hangers that have no hangers hanging from them.
Call a single hanger a hanger tree of height 1. Hanging one hanger on each side of a hanger gives a hanger tree of height 2. Repeating this, hanging a hanger tree of height on each side of a hanger gives a hanger tree of height . The closet is short, so you can hang clothes only on hanger trees of height 3 or less. A hanger tree of height 4 fits in the closet but is too tall to hang clothes below it, and a hanger tree of height 5 or more does not fit in the closet. You have nowhere else to put hangers, so you must use every hanger, and you do not need to place a hanger tree at every spot where a hanger can be hung.
Find the maximum number of clothes you can hang while placing hanger trees so that the conditions hold.
Input
The first line gives the number of spots where a hanger can be hung and the number of hangers, and . ()
Output
On the first line, print the maximum number of clothes you can hang. If there is no way to hang hangers at or fewer spots while satisfying the conditions above, print .
Hint
If you place hanger trees of heights 1, 2, 2, 3 in that order, you can hang 1, 2, 2, 4 clothes on them respectively.