0, 1, 2, Tree!
Contest: Codeforces Round 937 (Div. 4)
Difficulty rating: 1700
Tags: bitmasks, brute force, greedy, implementation, trees

Find the minimum height of a rooted tree$$$^{\dagger}$$$ with $$$a+b+c$$$ vertices that satisfies the following conditions:

- $$$a$$$ vertices have exactly $$$2$$$ children,
- $$$b$$$ vertices have exactly $$$1$$$ child, and
- $$$c$$$ vertices have exactly $$$0$$$ children.

The tree above is rooted at the top vertex, and each vertex is labeled with the number of children it has. Here $$$a=2$$$, $$$b=1$$$, $$$c=3$$$, and the height is $$$2$$$.

$$$^{\dagger}$$$ A rooted tree is a connected graph without cycles, with a special vertex called the root. In a rooted tree, among any two vertices connected by an edge, one vertex is a parent (the one closer to the root), and the other one is a child.

The distance between two vertices in a tree is the number of edges in the shortest path between them. The height of a rooted tree is the maximum distance from a vertex to the root.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The only line of each test case contains three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$0 \leq a, b, c \leq 10^5$$$; $$$1 \leq a + b + c$$$).

The sum of $$$a + b + c$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, if no such tree exists, output $$$-1$$$. Otherwise, output one integer — the minimum height of a tree satisfying the conditions in the statement.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first test case is pictured in the statement. It can be proven that you can't get a height smaller than $$$2$$$.

In the second test case, you can form a tree with a single vertex and no edges. It has height $$$0$$$, which is clearly optimal.

In the third test case, you can form a tree with two vertices joined by a single edge. It has height $$$1$$$, which is clearly optimal.

Example input:
10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1

Example output:
2
0
1
1
-1
3
6
-1
-1
3

Editorial:
Note that since the tree has $$$a+b+c$$$ vertices, all vertices have $$$0$$$, $$$1$$$, or $$$2$$$ children. Call a vertex a leaf if it has no children.
The idea is to "grow" the tree from the root by adding one or two vertices at a time. Formally:
• Start with a root (which is initially a leaf).
• Repeatedly add $$$1$$$ or $$$2$$$ children to a leaf. In total, add $$$2$$$ children $$$a$$$ times and $$$1$$$ child $$$b$$$ times.
• Every time we grow by adding $$$1$$$ child, the number of leaves does not change (since we lose one and gain one).
• Every time we grow by adding $$$2$$$ children, the number of leaves increases by one (since we lose one and gain two).
Otherwise we need to minimize the height. The idea is greedy: note that we should always grow by $$$2$$$ instead of $$$1$$$ when we have a choice, because it's clear that it will strictly decrease the height. Similarly, we should always grow the node closest to the root to minimize the height.
Thus we can just simulate the process described above growing by $$$2$$$ first and $$$1$$$ afterwards, which takes $$$\mathcal{O}(a+b+c)$$$ time.
Bonus: can you solve the problem in $$$\mathcal{O}(\log(a+b+c))$$$ time? Or even better?
A note on the implementation. You can store the number of "free" nodes on the current level and the next level in two variables, i.e. you don't need to store a whole tree at all. As you iterate through the current level, store the number of nodes in the next level.