$$$\mathcal Brief\;\mathcal Solution :$$$

A $$$n$$$-regular convex polygon is beautiful if and only if $$$n \% 4 = 0$$$. ($$$\%$$$ is the modular arithmetic symbol)

$$$\mathcal Brief\;\mathcal Solution :$$$

If the string $$$s$$$ is non-decreasing, then the answer is $$$s$$$ itself, otherwise the answer is $$$x+1$$$ zeroes and $$$y$$$ ones, where $$$x$$$ is the number of leading zeroes of the string $$$s$$$, and $$$y$$$ is the number of trailing ones of the string $$$s$$$.

$$$\mathcal Brief\; \mathcal Solution$$$ :

Give greatest elements to friends with $$$w_i = 1$$$. For the rest sort the elements in non-descending order of $$$a_i$$$ and sort the friends in non-ascending order of $$$w_i$$$ then give first $$$w_1-1$$$ elements to friend $$$1$$$, next $$$w_2-1$$$ elements to friend $$$2$$$ and so on, also give $$$k-i+1$$$-th greatest element to friend $$$i$$$ $$$(1 \le i \le k)$$$.

$$$\mathcal Brief \mathcal Solution$$$ :

Realize that a RDB of level $$$i$$$ is consisted of a vertex (the root of the RDB of level $$$i$$$) connected to the roots of two RDBs of level $$$i-2$$$ and a RDB of level $$$i-1$$$.

Run a DP and calculate the answer for each level $$$i$$$ ($$$ 3 \le i \le 2 \cdot 10^6$$$), then $$$dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?1:0)$$$.

$$$\mathcal Hints$$$ :

1. Find some greedy approaches. Its guessable that the problem is greedy.

2. Define $$$s_i$$$ for food $$$i$$$ equal to the number of guys who likes food $$$i$$$. Then find some condition which is enough to be sure that no answer exist.

3. See the last friend in a suitable permutation. What food will he eat?

4. Its easy to see that if $$$\forall 1 \le i \le m \Rightarrow s_i > w_i$$$, then no answer exist.

5. If a food $$$i$$$ exist such that $$$s_i \le w_i$$$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods.

$$$\mathcal Brief\;\mathcal Solution$$$ :

Define $$$s_i$$$ equal to the number of friends who likes food $$$i$$$. If for some $$$i$$$, $$$s_i \le w_i$$$ then place all the friends who likes food $$$i$$$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods

It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!!

$$$\mathcal Brief\; \mathcal Solution$$$ :

Define $$$win_{s,\,e}$$$ ($$$s \le e$$$) equal to $$$1$$$ if Lee can win the game when $$$s$$$ is written on the board, and equal to $$$0$$$ otherwise, also define $$$lose_{s,\,e}$$$ the same way.

Win :

If $$$e$$$ is odd then if $$$s$$$ is odd Lee loses otherwise Lee wins. So if $$$e$$$ is even then :

• if $$$\frac e 2 < s \le e$$$ then if $$$s$$$ is odd then Lee wins, otherwise Lee loses;
• if $$$\frac e 4 < s \le \frac e 2$$$ then Lee wins;
• if $$$s \le \frac e 4$$$ then the answer is equal to $$$win_{s,\, \lfloor \frac e 4 \rfloor}$$$.

Lose :

If $$$e < 2 \cdot s$$$, then Lee can immediately lose, otherwise the answer is equal to $$$\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$$$.