Editorial for Jealous Nobita

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

Else, Shizuka deletes a perfect binary tree having 2h12^h – 1 (where hh is the height of the tree) nodes which is an odd number. Now Dekisugi is left with odd – odd=evenodd\ –\ 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=oddeven\ –\ 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 NN nodes as answer.

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

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

So, if NN is even, Dekisugi wins.

    Statistics


    96% Solution Ratio

    ma5bahEarliest, 9M ago

    Karnis_052Fastest, 0.0s

    Sajjad_fc13Lightest, 0 B

    Coder_fahimShortest, 193B

    Toph uses cookies. By continuing you agree to our Cookie Policy.