Cách làm tối ưu cho bài toán này là sử dụng thuật toán chặt nhị phân để giải. Lúc đó ta sẽ có thể giải bài toán trong ~log_2(10^9)~ lượt (khoảng ~30~ lượt hỏi). Nhưng cách này không đủ để làm cho bạn có điểm tuyệt đối của bài (nếu làm theo phương án này bạn chỉ được tầm ~86\%~ số điểm mà thôi).

Thực ra, không có phương án nào có thể giải được tối ưu hơn ngoài chặt nhị phân. Chứng minh: Giả sử bạn luôn sử dụng ít hơn ~30~ lượt (trường hợp tệ nhất là ~29~ lượt) thì bạn sẽ chỉ phân biệt được ~2^{29}=536870912<10^9~ giá trị ~x~ khác nhau (do với mỗi thao tác hỏi, bạn chỉ có thể nhận về một trong hai giá trị là 0 hoặc 1).

Cách làm chuẩn cho bài toán này là hãy để ý kỹ vào cách tính điểm của bài toán. Điều kiện ~(\frac{69-cnt}{42})^2\ge 1~ sẽ xảy ra khi một trong hai trường hợp sau thỏa mãn:

• ~\frac{69-cnt}{42}\ge 1~.
• ~\frac{69-cnt}{42}\le -1~.

Nếu làm tối ưu, tức là bạn cố gắng làm cho ~\frac{69-cnt}{42}\ge 1~ thì sẽ không bao giờ làm được. Vì thế, cách tốt nhất là hãy làm cho ~\frac{69-cnt}{42}\le-1~. Điều này có thể xảy ra bằng việc hỏi ít nhất ~69+42=111~ câu hỏi. Bạn có thể spam ít nhất ~82~ lần hỏi chơi và dùng khoảng ~30~ lượt cho việc chặt nhị phân thì sẽ đủ để có thể AC.

Lưu ý nếu bạn hỏi quá nhiều thì bạn vẫn sẽ có thể ăn TLE.