Anna và Bruno là những cao thủ cờ bạc. Họ sẽ chơi một trò chơi với D-taro, người làm nhà cái của trò chơi.
Trong trò chơi này, Anna và Bruno ở hai phòng khác nhau. Họ chỉ có thể liên lạc với nhau bằng một thiết bị bị hỏng. D-taro đưa cho Anna một số nguyên. Mục tiêu của Anna và Bruno trong trò chơi là dùng thiết bị để truyền số nguyên được cho từ Anna đến Bruno.
Khi trò chơi bắt đầu, trước tiên Anna công bố một số nguyên $m$ từ $1$ đến $2\,000$, kể cả hai đầu mút. Sau đó họ chơi $Q$ lượt. Lượt thứ $i$ ($1 \le i \le Q$) diễn ra như sau.
- D-taro đưa cho Anna một số nguyên $A_i$.
- Anna nhập hai mảng $s_i,t_i$ vào thiết bị. Mỗi phần tử của hai mảng $s_i,t_i$ phải là $0$ hoặc $1$. Hai mảng $s_i,t_i$ phải có cùng độ dài, và độ dài này nằm trong khoảng từ $1$ đến $m$, kể cả hai đầu mút.
- Gọi $u_i$ là một mảng nhận được bằng cách trộn xen kẽ hai mảng $s_i$ và $t_i$ (xem bên dưới). Thiết bị gửi $u_i$ cho Bruno.
- Bruno gửi một số nguyên cho D-taro. Nếu số nguyên này bằng số nguyên $A_i$ mà D-taro đã đưa cho Anna, Anna và Bruno thắng lượt này.
Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno sao cho họ thắng cả $Q$ lượt.
Trộn xen kẽ
Ta nói một mảng $Z$ nhận được bằng cách trộn xen kẽ hai mảng $X$ và $Y$ nếu có thể chia các phần tử của $Z$ thành hai nhóm sao cho thỏa mãn hai điều kiện sau.
- Mảng gồm các phần tử thuộc nhóm thứ nhất, giữ nguyên thứ tự, bằng mảng $X$.
- Mảng gồm các phần tử thuộc nhóm thứ hai, giữ nguyên thứ tự, bằng mảng $Y$.
Ví dụ, mảng $Z=[1,1,1,0,0,0]$ nhận được bằng cách trộn xen kẽ $X=[1,1,0]$ và $Y=[1,0,0]$, vì mảng gồm các phần tử thứ nhất, thứ hai và thứ tư của $Z$, giữ nguyên thứ tự, là $[1,1,0]$, còn mảng gồm các phần tử thứ ba, thứ năm và thứ sáu của $Z$, giữ nguyên thứ tự, là $[1,0,0]$.
Ngược lại, nếu $X=[1,1,0]$, $Y=[1,0,0]$ và $Z=[0,0,0,1,1,1]$, thì $Z$ không nhận được bằng cách trộn xen kẽ $X$ và $Y$.
Chi tiết cài đặt
Bạn cần nộp hai tệp.
Tệp thứ nhất là Anna.cpp. Tệp này phải thực hiện chiến lược của Anna và cài đặt các hàm sau. Chương trình phải dùng chỉ thị tiền xử lý #include để bao gồm Anna.h.
int Declare()Hàm này được gọi một lần vào lúc bắt đầu.
- Giá trị trả về là số nguyên $m$ do Anna công bố.
- Số nguyên $m$ phải nằm trong khoảng từ $1$ đến $2\,000$, kể cả hai đầu mút. Nếu không thỏa mãn điều kiện này, chương trình bị chấm
Wrong Answer [1].
std::pair<std::vector<int>, std::vector<int> > Anna(long long A)Sau khi hàm
Declaređược gọi, hàm này được gọi $Q$ lần. Lần gọi thứ $i$ ($1 \le i \le Q$) tương ứng với bước 1 và bước 2 của lượt thứ $i$.- Tham số
Alà số nguyên $A_i$ mà D-taro đưa cho Anna. - Giá trị trả về là cặp gồm hai mảng $s_i,t_i$ mà Anna nhập vào thiết bị.
- Mỗi phần tử của hai mảng $s_i,t_i$ phải là $0$ hoặc $1$. Nếu không thỏa mãn điều kiện này, chương trình bị chấm
Wrong Answer [2]. - Độ dài của mỗi mảng $s_i,t_i$ phải nằm trong khoảng từ $1$ đến $m$, kể cả hai đầu mút. Nếu không thỏa mãn điều kiện này, chương trình bị chấm
Wrong Answer [3]. - Hai mảng $s_i,t_i$ phải có cùng độ dài. Nếu không thỏa mãn điều kiện này, chương trình bị chấm
Wrong Answer [4].
- Tham số
Tệp thứ hai là Bruno.cpp. Tệp này phải thực hiện chiến lược của Bruno và cài đặt hàm sau. Chương trình phải dùng chỉ thị tiền xử lý #include để bao gồm Bruno.h.
long long Bruno(std::vector<int> u)Sau khi Anna nhập các mảng vào thiết bị, hàm này được gọi một lần. Tổng cộng, hàm được gọi $Q$ lần. Lần gọi thứ $i$ ($1 \le i \le Q$) tương ứng với bước 3 và bước 4 của lượt thứ $i$.
- Tham số
ulà mảng $u_i$ mà thiết bị gửi cho Bruno trong lượt thứ $i$. - Giá trị trả về là số nguyên Bruno gửi cho D-taro.
- Giá trị trả về phải bằng số nguyên $A_i$ mà D-taro đưa cho Anna. Nếu không thỏa mãn điều kiện này, chương trình bị chấm
Wrong Answer [5].
- Tham số
Lưu ý quan trọng
- Chương trình có thể cài đặt các hàm khác để dùng nội bộ hoặc sử dụng biến toàn cục. Các tệp được nộp sẽ được biên dịch cùng trình chấm thành một tệp thực thi duy nhất. Tất cả biến toàn cục và hàm nội bộ phải được khai báo trong một không gian tên vô danh để tránh xung đột với các tệp khác. Khi chấm, chương trình được chạy thành hai tiến trình của Anna và Bruno. Tiến trình của Anna và tiến trình của Bruno không thể dùng chung biến toàn cục.
- Chương trình không được sử dụng đầu vào chuẩn và đầu ra chuẩn, cũng không được liên lạc với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, chương trình có thể xuất thông tin gỡ lỗi ra đầu ra lỗi chuẩn.
Biên dịch và chạy thử
Bạn có thể tải từ trang web cuộc thi một tệp nén chứa trình chấm mẫu để kiểm thử chương trình của mình. Tệp nén cũng chứa mã nguồn mẫu cho chương trình của bạn.
Trình chấm mẫu nằm trong tệp grader.cpp. Để kiểm thử chương trình, hãy đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng một thư mục và chạy lệnh sau để biên dịch chương trình.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
Khi biên dịch thành công, tệp thực thi grader được tạo ra.
Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu chạy dưới dạng một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.
Dữ liệu vào của trình chấm mẫu
Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.
$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$
Dữ liệu ra của trình chấm mẫu
Trình chấm mẫu xuất thông tin sau ra đầu ra chuẩn (dấu ngoặc kép chỉ để làm rõ).
- Nếu chương trình được chấm là đúng, trình chấm ghi giá trị trả về $m$ của hàm
Declare, chẳng hạnAccepted: 2000. - Nếu chương trình bị chấm một trong các loại đáp án sai, trình chấm mẫu ghi loại đó, chẳng hạn
Wrong Answer [1].
Nếu chương trình thỏa mãn điều kiện của nhiều loại đáp án sai, trình chấm mẫu chỉ báo một loại.
Khi chạy trình chấm mẫu, phép trộn xen kẽ cho mỗi lượt được tính bằng các số giả ngẫu nhiên. Kết quả của chúng không thay đổi giữa các lần chạy. Để thay đổi hạt giống của bộ sinh số giả ngẫu nhiên, hãy chạy trình chấm mẫu như sau.
./grader 2022
Đối số đầu tiên phải là một số nguyên.
Giới hạn
- $1 \le Q \le 1\,000$.
- $1 \le A_i \le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1 \le i \le Q$).
Nhiệm vụ con
- (5 điểm) $A_i \le 2\,000$ ($1 \le i \le Q$).
- (5 điểm) $A_i \le 4\,000\,000$ ($1 \le i \le Q$).
- (3 điểm) $A_i \le 10\,000\,000\ (=10^7)$ ($1 \le i \le Q$).
- (12 điểm) $A_i \le 100\,000\,000\ (=10^8)$ ($1 \le i \le Q$).
- (15 điểm) $A_i \le 100\,000\,000\,000\ (=10^{11})$ ($1 \le i \le Q$).
(60 điểm) Không có ràng buộc bổ sung. Với nhiệm vụ con này, điểm của bạn được tính như sau.
- Gọi $m^*$ là giá trị lớn nhất trong các số nguyên $m$ mà Anna công bố trên tất cả các bộ dữ liệu kiểm thử của nhiệm vụ con này.
- Điểm của bạn được tính như sau.
| Giá trị của $m^*$ | Điểm |
|---|---|
| $201 \le m^* \le 2\,000$ | $40-25\times\log_{10}\left(\frac{m^*}{200}\right)$ điểm (làm tròn xuống số nguyên gần nhất) |
| $161 \le m^* \le 200$ | 40 điểm |
| $156 \le m^* \le 160$ | 44 điểm |
| $151 \le m^* \le 155$ | 48 điểm |
| $146 \le m^* \le 150$ | 52 điểm |
| $141 \le m^* \le 145$ | 56 điểm |
| $m^* \le 140$ | 60 điểm |
Ví dụ giao tiếp
Dưới đây là dữ liệu vào mẫu cho trình chấm mẫu và các lời gọi hàm tương ứng.
Dữ liệu vào 1
2 42 2000
Các lời gọi hàm mẫu
| Lời gọi | Giá trị trả về |
|---|---|
Declare() |
4 |
Anna(42) |
([0, 0, 1, 0], [1, 1, 0, 1]) |
Bruno([1, 0, 0, 1, 0, 1, 0, 1]) |
42 |
Anna(2000) |
([0, 1], [0, 0]) |
Bruno([0, 0, 1, 0]) |
2000 |
Trong dữ liệu vào mẫu này có $Q\ (=2)$ lượt. Ở lượt thứ $1$, D-taro đưa cho Anna số nguyên $A_1\ (=42)$. Ở lượt thứ $2$, D-taro đưa cho Anna số nguyên $A_2\ (=2000)$.
Dữ liệu vào mẫu này thỏa mãn các ràng buộc của tất cả các nhiệm vụ con.