/** A binary tree in which each node has two children. */ public class BinaryTree { private Node root;

/** Constructs an empty tree. */ public BinaryTree() { root = null; }

/** Constructs a tree with one node and no children. @param rootData the data for the root */ public BinaryTree(Object rootData) { root = new Node(); root.data = rootData; root.left = null; root.right = null; }

/** Constructs a binary tree. @param rootData the data for the root @param left the left subtree @param right the right subtree */ public BinaryTree(Object rootData, BinaryTree left, BinaryTree right) { root = new Node(); root.data = rootData; root.left = null; root.right = null; if (left != null) { root.left = left.root; } if (right != null) { root.right = right.root; } }

class Node { public Object data; public Node left; public Node right; }

/** Returns the height of the subtree whose root is the given node. @param n a node or null @return the height of the subtree, or 0 if n is null */ private static int height(Node n) { if (n == null) { return 0; } else { return 1 + Math.max(height(n.left), height(n.right)); } }

/** Returns the height of this tree. @return the height */ public int height() { return height(root); }

/** Checks whether this tree is empty. @return true if this tree is empty */ public boolean isEmpty() { return root == null; }

/** Gets the data at the root of this tree. @return the root data */ public Object data() { return root.data; }

/** Gets the left subtree of this tree. @return the left child of the root */ public BinaryTree left() { BinaryTree result = new BinaryTree(); result.root = root.left; return result; }

/** Gets the right subtree of this tree. @return the right child of the root */ public BinaryTree right() { BinaryTree result = new BinaryTree(); result.root = root.right; return result; } }

=======================================================

import java.util.*;

public class PoD {

//============================================================================= /** * Returns true if the game tree (binary tree) can be won * where the last player to move wins * @param bTree BinaryTree of interest * @return */

public static boolean gameCanBeWon(BinaryTree bTree) { boolean canWin;

/* If both left and right subtrees are empty: - player has NO moves - is not winnable */

/* If both the left or right subtrees can be won (i.e. all positions you move to allow the other player to win), you can not win.

Otherwise, you have a winning move: - move to the subtree that can not be won by your opponent - the game can be won! */

return canWin;

} //=============================================================================

public static void main( String [] args ) {

Scanner in = new Scanner( System.in );

int i = in.nextInt();

BinaryTree newBT = makeBT(i);

boolean canBeWon = gameCanBeWon(newBT);

if (canBeWon) { System.out.println("You can win!"); //if you play perfectly! } else { System.out.println("You can not win this game"); //Under perfect play! }

in.close();

System.out.print("END OF OUTPUT"); }

public static BinaryTree makeBT(int n) { BinaryTree b; if (n>0) { b = new BinaryTree(n,makeBT(n-1),makeBT(n-2)); //System.out.println(n+":"+(n-1)+"|"+(n-2)); } else { b = new BinaryTree(0,null,null); //System.out.println(n+":null|null"); }

return b;

} }

================================

SampleInput.in = 2