The cows have structured their company in the form of a binary tree, where each employee manages two direct subordinates (a "left" and a "right" subordinate). For each employee E, the total number of employees in E's left subtree is either equal to or one greater than the total number in E's right subtree. Each employee has a distinct integer ID in the range 1..N, with the CEO (the root) having ID 1.

You can interactively query any employee to determine the IDs of her two subordinates (responses of 0 indicate no subordinate). The cows have lost track of the exact value of N (1 <= N <= 10^100). Please compute N. Your program is limited to making at most 70,000 queries.

NOTE: This is an INTERACTIVE problem (the program queries a grader over stdin/stdout). It cannot be auto-judged with the standard file-based test data on RiseOJ; this entry is provided for archival/statement reference only.

Interactive: write an employee ID to stdout to query; read back two integers (the IDs of the left and right subordinates). Finish by printing "Answer N".

Print "Answer N" as your final line of output, where N is the total number of employees.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > US Open > Gold