Mệt mỏi vì phải lọc qua các kết quả tìm kiếm trên web dành cho những loài vật nuôi khác, đàn bò quyết định ra mắt công cụ tìm kiếm của riêng mình. Không may, do vô cùng thiếu kinh nghiệm trong việc quản lý các dự án phần mềm lớn, số nhân viên \(N\) (\(1 \le N \le 10^{100}\)) trong công ty của chúng cuối cùng lại lớn hơn đáng kể so với kế hoạch ban đầu. Để tìm một cái tên phù hợp cho công ty, đàn bò lấy cảm hứng từ cận trên của \(N\) và quyết định đặt tên công ty là "Googol", tên gọi của số \(10^{100}\).

Trong nỗ lực tuyệt vọng nhằm cải thiện cơ cấu quản lý của công ty, đàn bò tổ chức công ty dưới dạng một cây nhị phân, trong đó mỗi nhân viên chịu trách nhiệm quản lý hai cấp dưới trực tiếp, được gọi là cấp dưới "trái" và "phải" theo cấu trúc cây. Để cân bằng khối lượng quản lý của mỗi nhân viên, đàn bò sắp xếp cây tổ chức sao cho với mỗi nhân viên E, tổng số nhân viên trong cây con trái của E hoặc bằng, hoặc lớn hơn đúng một so với tổng số nhân viên trong cây con phải của E.

Giao thức tương tác

Mỗi nhân viên có một mã số nguyên phân biệt trong khoảng \(1 \ldots N\), trong đó CEO (gốc của cây) có mã số 1. Bạn có thể tương tác để truy vấn bất kỳ nhân viên nào nhằm xác định mã số của hai cấp dưới của cô ấy. Để thực hiện truy vấn, hãy ghi mã số của nhân viên đó ra luồng đầu ra chuẩn (stdout), theo sau bởi một ký tự xuống dòng. Phản hồi bạn nhận được sẽ là một dòng chứa hai số nguyên, lần lượt là mã số của cấp dưới trái và cấp dưới phải của nhân viên này. Cả hai mã số có thể bằng 0 nếu nhân viên đó không có cấp dưới, hoặc chỉ mã số bên phải có thể bằng 0 nếu nhân viên đó chỉ có cấp dưới trái (lưu ý rằng do điều kiện cân bằng ở trên, một nhân viên không thể có cấp dưới phải mà không có cấp dưới trái).

Không may, đàn bò đã quên mất giá trị chính xác của \(N\). Hãy tính số này và in Answer N (theo sau bởi một ký tự xuống dòng) làm dòng cuối cùng của đầu ra. Chương trình của bạn được phép thực hiện nhiều nhất \(70{,}000\) truy vấn và có giới hạn thời gian chạy 4 giây (8 giây đối với Java hoặc Python).

Tương tác mẫu

Dưới đây là một ví dụ về một lượt tương tác có thể xảy ra giữa chương trình của bạn và trình chấm:

CHƯƠNG TRÌNH CỦA BẠN: 1
TRÌNH CHẤM: 4 3
CHƯƠNG TRÌNH CỦA BẠN: 4
TRÌNH CHẤM: 2 0
CHƯƠNG TRÌNH CỦA BẠN: 3
TRÌNH CHẤM: 0 0
CHƯƠNG TRÌNH CỦA BẠN: Answer 4

     1
   4   3
 2

Lưu ý kỹ thuật: bài toán này được chấm bằng một trình chấm tương tác, một phần mới trong hệ thống chấm của chúng tôi. Nếu bạn gặp hành vi nào có vẻ là sự cố kỹ thuật với trình chấm, vui lòng báo tới [email protected]. Chúng tôi cho rằng điều này không cần thiết, nhưng nếu mã của bạn có vẻ bị treo trong lúc chấm, hãy thử thêm các lệnh xả luồng đầu ra (chẳng hạn fflush(stdout) hoặc cout.flush()), phòng trường hợp dữ liệu bị lưu đệm ngoài dự kiến và không đến được trình chấm. Nếu việc này có vẻ cần thiết để mã của bạn hoạt động, vui lòng gửi thông báo tới [email protected] để chúng tôi có thể khắc phục sự cố trong tương lai.

Nguồn

USACO 2015 US Open, Gold — Googol. Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=552