Đây là bài toán tương tác, thí sinh chỉ có thể giải bằng ngôn ngữ C++.

Bạn đang tham gia trò chơi ``thử thách đoán số''. Để chinh phục giải thưởng độc đắc siêu to khổng lồ, bạn cần tìm ra mật mã của chương trình là một cặp số nguyên dương \((x, y)\). Chương trình cho bạn một manh mối: hai số này thỏa mãn \(1 \leq x, \sqrt[3]{y} \leq 100\) và \(x \leq y\).

Để giúp bạn tìm ra mật mã, MC sẽ cung cấp thêm thông tin. Bạn được phép đưa cho MC một số nguyên \(k\) thỏa mãn \(1 \leq k \leq 10^{18}\). Khi đó, MC sẽ ngay lập tức cho bạn biết có hay không hai số nguyên không âm \(\alpha, \beta\) thỏa mãn \(k = \alpha \cdot x + \beta \cdot y\) (nhưng không cho biết cụ thể hai số \(\alpha, \beta\) nào). Vì tính kiên nhẫn của MC có hạn, bạn chỉ có thể làm điều này không quá \(10^6\) lần.

Cũng có đôi khi, chương trình cố tình gài mật mã là một cặp số bẫy để khiến bạn không thể tìm được. Nếu bạn tinh ý và phát hiện được ra ý đồ này, bạn vẫn nhận được giải độc đắc. Một cặp số \((x, y)\) được gọi là cặp số bẫy khi và chỉ khi tồn tại một cặp số nguyên \((\chi, \psi)\) sao cho:

• \(1 \leq \chi, \sqrt[3]{\psi} \leq 100\) và \(\chi\leq \psi\)
• \(x \neq \chi\) hoặc \(y \neq \psi\)
• Với mọi số nguyên \(k\) thỏa mãn \(1 \leq k \leq 10^{18}\), nếu bạn đưa số \(k\) cho MC, thông tin từ MC là giống nhau trong cả hai kịch bản mật mã là \((x, y)\) và \((\chi, \psi)\).

Số lần bạn lấy thông tin từ MC càng ít, giải thưởng của bạn càng lớn. Hãy tìm ra mật mã với số lần lấy thông tin càng ít càng tốt nhé!

Chi tiết cài đặt

Thí sinh cần cài đặt hàm pair<int, int> play(int subtask_id): Hàm nhận vào tham số subtask_id là số thứ tự của subtask chứa test này. Hàm cần trả về một pair thể hiện mật mã trong đó first là \(x\) và second là \(y\), hoặc trả về \(\{-1, -1\}\) nếu mật mã này là một cặp số bẫy.

Thí sinh được cung cấp thư viện guess.h bên trong có cài đặt sẵn hàm bool check(long long k): Hàm nhận vào một số nguyên \(k\) thỏa mãn \(1 \leq k \leq 10^{18}\) và trả về true khi và chỉ khi tồn tại hai số nguyên không âm \(\alpha, \beta\) sao cho \(k = \alpha \cdot x + \beta \cdot y\).

Mỗi test có không quá \(100\) bộ dữ liệu. Hàm play được gọi một lần cho mỗi bộ dữ liệu.

Lưu ý:

• Thí sinh cần có dòng lệnh khai báo thư viện #include "guess.h" ở dòng đầu tiên của chương trình.
• File mã nguồn của thí sinh không được chứa hàm main. Việc viết hàm main có thể gây ra lỗi biên dịch cho bài làm của thí sinh.
• Thí sinh có thể định nghĩa thêm hàm hoặc khai báo thêm các biến toàn cục nếu cần.
• Thí sinh không được đọc dữ liệu từ thiết bị vào chuẩn hay bất cứ tệp tin nào, cũng như không được in ra thiết bị ra chuẩn hay bất kì tệp tin nào.
• Thí sinh sẽ nhận được kết quả chấm là Kết quả sai nếu như tham số truyền vào hàm check không hợp lệ, hàm check được gọi nhiều hơn \(10^6\) lần trong một bộ dữ liệu, hay kết quả trả về của hàm play không chính xác.
• Vui lòng tham khảo chương trình mẫu tại đây, thư viện mẫu tại đây và xem hướng dẫn về các bài toán tương tác tại video này của GSPVHCUTE

Ràng buộc

Bộ test được chia làm năm subtask như sau:

• Subtask \(1\) (\(20\) điểm): \(x = 2\)
• Subtask \(2\) (\(15\) điểm): \(\sqrt[3]{y} = 100\)
• Subtask \(3\) (\(15\) điểm): \(\sqrt[1]{y} \leq 100\)
• Subtask \(4\) (\(20\) điểm): \(\sqrt[2]{y} \leq 100\)
• Subtask \(5\) (\(30\) điểm): Không có ràng buộc gì thêm.

Với mỗi test:

• Nếu bạn giải sai ít nhất một bộ dữ liệu, bao gồm nhưng không hạn chế ở các việc như tham số truyền vào hàm \(\texttt{check}\) không hợp lệ, hàm \(\texttt{check}\) được gọi nhiều hơn \(10^6\) lần, kết quả trả về của hàm \(\texttt{play}\) không chính xác; bạn sẽ được \(0\) điểm và nhận kết quả chấm là \(\texttt{Kết quả sai}\).
• Ngược lại, gọi \(\rho\) là số lần gọi hàm \(\texttt{check}\) nhiều nhất trong một bộ dữ liệu, số điểm bạn nhận được là \(\sqrt{\frac{789}{\max(789, \rho)}}\).

Điểm tối đa của một test là \(1\). Điểm của bài nộp là tông điểm đạt được ở tất cả các test.

Ví dụ

Dưới đây là một ví dụ về sự tương tác. Trong ví dụ này, mật mã ẩn là \(x = 7\) và \(y = 22\). Khi đó, hàm play(1) được gọi:

• Lệnh gọi hàm guess(97) trả về false. Không tồn tại hai số nguyên không âm \(\alpha, \beta\) thỏa mãn \(97 = \alpha \cdot 7 + \beta \cdot 22\).
• Lệnh gọi hàm guess(227) trả về true. Ta có \(227 = 23 \cdot 7 + 3 \cdot 22\).
• Hàm cần trả về giá trị \(\{7, 22\}\).