New Year Cake

Core Idea

The cake shape is completely fixed. If it has $n$ layers, their sizes are:

$$1, 2, 4, 8, \dots, 2^{n-1}$$

The only freedom Monocarp has is the color of the top layer. After that, everything is forced because colors must alternate.

So there are only two possible valid color patterns:

• top layer is white: white gets layers $1,4,16,\dots$, dark gets $2,8,32,\dots$
• top layer is dark: dark gets layers $1,4,16,\dots$, white gets $2,8,32,\dots$

That's it. No sneaky arrangement. No "maybe put two dark layers together because it helps" nonsense. The statement explicitly says alternating, so adjacent equal colors are illegal.

Why Brute Force Is Enough

The constraints are tiny in the important way: $a,b \le 10^6$.

The total chocolate needed for $n$ layers is:

$$1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$$

Even with both chocolate supplies combined, we have at most $2 \cdot 10^6$ kg. Since $2^{21}-1 = 2097151$, the answer is around $20$ at most. That is baby brute force territory.

For every test case, we can simulate layers from top to bottom. For each possible starting color, keep track of how much white and dark chocolate has been used so far.

When adding layer $i$, its size is $2^i$.

If the top starts white:

• even $i$ layers are white
• odd $i$ layers are dark

If the top starts dark, the roles swap.

After adding each layer, check whether the used white chocolate is at most $a$ and the used dark chocolate is at most $b$. If yes, update the answer.

Algorithm

For each test case:

1. Read $a,b$.
2. Set ans = 0.
3. Try both starting colors.
4. For each starting color, simulate layers while powers of two are reasonable.
5. Track white and dark usage.
6. Whenever white <= a and dark <= b, update ans.
7. Print ans.

We can loop for, say, $0$ to $30$ layers. That is more than enough because $2^{30}$ is way beyond the constraints. Using long long keeps everything chill.

Correctness Proof

We prove the algorithm outputs the maximum possible number of layers.

First, for any fixed number of layers, the layer sizes are fixed by the statement: the top layer has size $1$, and every next layer is twice as large. Therefore the sizes must be exactly $1,2,4,\dots,2^{n-1}$.

Second, once the color of the top layer is chosen, every other layer color is forced because adjacent layers must alternate. Thus there are exactly two possible valid colorings for any $n$: one starting with white and one starting with dark.

The algorithm checks both of these possible starting colors. For each one, it simulates the exact chocolate usage layer by layer. Therefore, for every possible valid cake, the algorithm checks that cake's chocolate requirements.

Whenever the algorithm says $n$ layers are possible, it has found one of the two valid alternating colorings whose white usage is at most $a$ and dark usage is at most $b$. So that cake is truly buildable.

Whenever some $n$-layer cake is buildable, it must use one of the two starting colors, and the algorithm checks that exact pattern. So the algorithm will mark $n$ as possible.

Since the algorithm records the largest possible $n$ it sees, it outputs exactly the maximum number of layers.

Complexity

For each test case, we check only a constant number of layers, about $31$, for two starting colors.

So the time complexity is:

$$O(t)$$

with a very small constant.

Memory usage is:

$$O(1)$$