# Editorial for Jealous Nobita

Let $N$ is odd. If it’s a complete binary tree, Shizuka wins by deleting it at once.

Else, Shizuka deletes a perfect binary tree having $2^h – 1$ (where $h$ is the height of the tree) nodes which is an odd number. Now Dekisugi is left with $odd\ –\ odd = even$ number of nodes.

Now Dekisugi deletes a perfect binary tree with an odd number of nodes. So, Shizuka is left with $even\ –\ odd = odd$ number of nodes.

Now it's the same as the initial state, Shizuka having a binary tree with an odd number of nodes. Eventually Shizuka will be left with a complete binary tree with an odd number of nodes for sure. Because every time Dekisugi will be left with an even number of nodes and he can’t delete it as there’s no perfect binary tree with even number of nodes. Print any binary tree with $N$ nodes as answer.

So, it’s proved that, whoever gets an odd binary tree wins at the end.

Now, if $N$ is even, Shizuka deletes a perfect binary tree with an odd number of nodes. Dekisugi is left with $even\ –\ odd = odd$ number of nodes. We’ve proved that whoever gets an odd binary tree wins at last.

So, if $N$ is even, Dekisugi wins.

### Statistics

96% Solution Ratio

ma5bahEarliest, 9M ago

Karnis_052Fastest, 0.0s 