Ban giám khảo đã chọn một số nguyên $x$ trong khoảng $[1, n]$. Nhiệm vụ của bạn là đoán số đó. Để không phải đoán mò, bạn có thể đặt các câu hỏi. Trong mỗi câu hỏi, bạn có thể đưa ra một số nguyên $y$ trong khoảng $[0, c]$, và chúng tôi sẽ trả lời bằng số lượng ước của số $x + y$. Để tăng độ khó, trong một lần chạy chương trình, bạn sẽ phải giải $t$ trường hợp kiểm thử. Tổng số câu hỏi bạn có thể đặt ra bị giới hạn bởi $q$.
Giao tiếp
Đây là bài toán tương tác. Bạn cần viết một chương trình giao tiếp với Ban giám khảo thông qua thư viện được cung cấp. Để sử dụng thư viện, bạn cần thêm vào chương trình của mình:
- C++:
#include "dzilib.h" - Python:
from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
Thư viện cung cấp các hàm sau:
GetT()– Trả về tham số $t$ – số lượng trường hợp kiểm thử cần giải.GetN()– Trả về tham số $n$ – giới hạn trên của các giá trị ẩn $x$.GetQ()– Trả về tham số $q$ – giới hạn tổng số câu hỏi bạn có thể đặt ra trong tất cả $t$ trường hợp kiểm thử.GetC()– Trả về tham số $c$ – giới hạn trên cho các giá trị $y$ mà bạn đưa ra.Ask(y)– Trả về số lượng ước dương của số ẩn $x$ cộng thêm $y$. Phải thỏa mãn $0 \le y \le c$.Answer(z)– Thông báo cho thư viện rằng theo bạn, giá trị ẩn $x$ là $z$. Hàm này không trả về giá trị (trong C++, hàm có kiểuvoid).
Trong ngôn ngữ Python, tất cả các tham số của hàm thư viện và giá trị trả về đều là kiểu số nguyên. Trong ngôn ngữ C++, các kiểu dữ liệu đầu vào và đầu ra của hàm giống như trong thư viện mẫu được cung cấp, xem thêm chi tiết trong phần Thí nghiệm.
Tại mọi thời điểm chương trình hoạt động (ngoại trừ lúc kết thúc), sẽ có một trường hợp kiểm thử đang hoạt động. Trường hợp kiểm thử đầu tiên được kích hoạt ngay sau khi chương trình bắt đầu. Khi một trường hợp kiểm thử đang hoạt động, bạn có thể đặt câu hỏi bằng hàm Ask. Khi bạn xác định được giá trị ẩn $x$, bạn có thể đưa ra câu trả lời bằng hàm Answer, và thư viện sẽ xác minh nó. Nếu giá trị đưa ra không chính xác, thư viện sẽ kết thúc chương trình với kết quả "błędna odpowiedź" (sai đáp án). Nếu giá trị tham số chính xác, hàm sẽ kết thúc; nếu trường hợp kiểm thử vừa giải không phải là trường hợp cuối cùng, trường hợp tiếp theo sẽ được kích hoạt ngay lập tức. Sau khi trả lời trường hợp kiểm thử cuối cùng, bạn nên kết thúc chương trình. Nếu bạn không làm vậy và cố gắng sử dụng hàm Ask hoặc Answer, bạn sẽ nhận được kết quả "błędna odpowiedź".
Bạn có thể sử dụng các hàm GetT, GetN, GetQ và GetC tại bất kỳ thời điểm nào và các giá trị trả về của chúng sẽ không thay đổi. Các hàm này không tính vào giới hạn số câu hỏi nhưng sẽ tiêu tốn thời gian xử lý. Giá trị $q$ chỉ giới hạn số lần gọi hàm Ask. Ngay khi bạn vượt quá tổng số câu hỏi cho phép, thư viện sẽ kết thúc chương trình và bạn sẽ nhận được kết quả "błędna odpowiedź".
Không được đọc bất kỳ dữ liệu nào từ đầu vào chuẩn (standard input) hoặc ghi bất kỳ dữ liệu nào ra đầu ra chuẩn (standard output). Các hành vi cố tình can thiệp vào hoạt động nội bộ của thư viện chấm bài đều bị cấm.
Các giá trị ẩn $x$ trong tất cả các bài kiểm thử và thứ tự của chúng đã được xác định trước. Điều này có nghĩa là thư viện mà chương trình của bạn giao tiếp sẽ không "độc hại" và sẽ không điều chỉnh hành vi của nó dựa trên hoạt động của chương trình của bạn.
Các giới hạn được nêu trong đề bài chỉ áp dụng cho thời gian và bộ nhớ mà chương trình của bạn sử dụng. Tuy nhiên, thời gian hoạt động của thư viện và bộ nhớ mà nó sử dụng có thể phụ thuộc vào bài kiểm thử và hành vi cụ thể của chương trình của bạn. Vì lý do này, các giới hạn thời gian và bộ nhớ trên SIO2 hơi cao hơn so với những gì được nêu trong đề bài.
Ví dụ
Dữ liệu vào 1
2 1000000 10000 1000000000000000 1000 1
Dữ liệu ra 1
GetT() GetN() GetQ() GetC() Ask(1) Ask(24) Answer(1000) GetT() Answer(1)
Ghi chú
Trong ví dụ trên, $t = 2, n = 10^6, q = 10^4, c = 10^{15}$, các giá trị ẩn lần lượt là $1000$ và $1$. Đã có 2 câu hỏi Ask được đặt ra, nằm trong giới hạn 10 000 câu hỏi. Hãy nhớ rằng tổng số câu hỏi được tính cho tất cả các trường hợp kiểm thử trong một bài kiểm thử.
Nhiệm vụ con
Trong một nhóm bài kiểm thử, tất cả các bài kiểm thử đều có cùng các giá trị $t, n, q$ và $c$ như bảng dưới đây:
| Số nhóm | $t$ | $n$ | $q$ | $c$ |
|---|---|---|---|---|
| 1 | 50 | $10^5$ | 50 000 | $10^{12}$ |
| 2 | 50 | $10^6$ | 5 000 | $10^{12}$ |
| 3 | 10 | $10^9$ | 50 000 | $10^{12}$ |
| 4 | 10 | $10^{14}$ | 5 000 | $10^{17}$ |
| 5 | 10 | $10^{14}$ | 2 000 | $10^{17}$ |
| 6 | 10 | $10^{14}$ | 1 300 | $10^{17}$ |
| 7 | 10 | $10^{14}$ | 950 | $10^{17}$ |
| 8 | 10 | $10^{14}$ | 820 | $10^{17}$ |
| 9 | 10 | $10^{14}$ | 750 | $10^{17}$ |
| 10 | 10 | $10^{14}$ | 720 | $10^{17}$ |
Bài kiểm thử ví dụ không thuộc bất kỳ nhóm nào. Bạn có thể giải nó, nhưng hãy lưu ý rằng có thể đạt được điểm tối đa mà không cần giải bài kiểm thử này.
Chi tiết cài đặt
Các lời giải sai mẫu và thư viện mẫu bằng ngôn ngữ C++ và Python nằm trong các tệp lưu trữ tại mục Pliki trên SIO2. Các lời giải và thư viện này minh họa các kiểu dữ liệu trả về và nhận vào của tất cả các hàm. Các thư viện mẫu có thể khác về hành vi so với thư viện sẽ được sử dụng để chấm bài và có thể không đáp ứng các giả định của bài toán. Chúng chỉ nhằm mục đích hiển thị cách tương tác với chương trình.
Lời giải dzi.cpp bằng ngôn ngữ C++ có thể được biên dịch như sau:
g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20
Bạn cần đảm bảo rằng các tệp dzilib.h và dzilib.cpp nằm trong cùng thư mục với lời giải.
Lời giải dzi.py có thể được chạy bằng lệnh:
python dzi.py
Bạn cần đảm bảo rằng tệp dzilib.py nằm trong cùng thư mục với lời giải.
Sau khi khởi chạy, ngay từ đầu chương trình, thư viện sẽ nhận các giá trị $t, n, q$ và $c$ lần lượt từ đầu vào chuẩn, sau đó là các giá trị ẩn $x$ tiếp theo. Tệp đầu vào tương ứng với bài kiểm thử ví dụ nằm trong cả hai tệp lưu trữ với tên dzi0.in.