Anna và Bruno là hai cao thủ cá cược. Họ chơi một trò chơi với D-taro, người chia bài.

Trong trò chơi này, Anna và Bruno ở hai phòng khác nhau. Họ chỉ có thể liên lạc qua 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 là dùng thiết bị để truyền số nguyên đó từ Anna sang 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 \(2000\), 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:

1. D-taro đưa cho Anna số nguyên \(A_i\).
2. Anna đưa hai dãy \(s_i,t_i\) vào thiết bị. Mỗi phần tử của hai dãy phải là \(0\) hoặc \(1\). Hai dãy phải có cùng độ dài, và độ dài đó phải nằm trong khoảng từ \(1\) đến \(m\), kể cả hai đầu mút.
3. Thiết bị tạo một dãy \(u_i\) bằng cách trộn xen kẽ hai dãy \(s_i,t_i\) như mô tả dưới đây, rồi gửi \(u_i\) cho Bruno.
4. Bruno gửi một số nguyên cho D-taro. Anna và Bruno thắng lượt này nếu số nguyên đó bằng \(A_i\).

Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để họ thắng cả \(Q\) lượt.

Phép trộn xen kẽ

Ta nói dãy \(Z\) được tạo bằng cách trộn xen kẽ (riffle shuffle) hai dãy \(X,Y\) nếu có thể chia các phần tử của \(Z\) thành hai nhóm sao cho:

• Các phần tử thuộc nhóm thứ nhất, giữ nguyên thứ tự xuất hiện trong \(Z\), tạo thành dãy \(X\).
• Các phần tử thuộc nhóm thứ hai, giữ nguyên thứ tự xuất hiện trong \(Z\), tạo thành dãy \(Y\).

Ví dụ, \(Z=[1,1,1,0,0,0]\) có thể được tạo từ \(X=[1,1,0]\) và \(Y=[1,0,0]\): các phần tử thứ \(1,2,4\) của \(Z\) tạo thành \(X\), còn các phần tử thứ \(3,5,6\) tạo thành \(Y\).

Ngược lại, với \(X=[1,1,0]\), \(Y=[1,0,0]\) và \(Z=[0,0,0,1,1,1]\), không thể tạo \(Z\) bằng cách trộn xen kẽ \(X,Y\).

Chi tiết cài đặt

Bạn cần nộp hai tệp.

Tệp thứ nhất là Anna.cpp, cài đặt chiến lược của Anna. Tệp này phải dùng chỉ thị #include để nạp Anna.h và cài đặt các hàm sau:

int Declare();
std::pair<std::vector<int>, std::vector<int> > Anna(long long A);

Hàm Declare được gọi đúng một lần lúc bắt đầu. Giá trị trả về là số nguyên \(m\) do Anna công bố. Nếu \(m\) không nằm trong đoạn \([1,2000]\), chương trình bị chấm Wrong Answer [1].

Sau lời gọi Declare, hàm Anna được gọi \(Q\) lần. Lời gọi thứ \(i\) tương ứng với bước \(1\) và bước \(2\) của lượt thứ \(i\):

• Tham số A là số nguyên \(A_i\) do D-taro đưa cho Anna.
• Giá trị trả về là cặp hai dãy \(s_i,t_i\) được đưa vào thiết bị.
• Nếu có phần tử nào của \(s_i\) hoặc \(t_i\) khác \(0\) và \(1\), chương trình bị chấm Wrong Answer [2].
• Độ dài của mỗi dãy phải nằm trong đoạn \([1,m]\). Nếu không, chương trình bị chấm Wrong Answer [3].
• Hai dãy phải có cùng độ dài. Nếu không, chương trình bị chấm Wrong Answer [4].

Tệp thứ hai là Bruno.cpp, cài đặt chiến lược của Bruno. Tệp này phải dùng chỉ thị #include để nạp Bruno.h và cài đặt hàm sau:

long long Bruno(std::vector<int> u);

Sau mỗi lần Anna đưa các dãy vào thiết bị, hàm Bruno được gọi một lần, tổng cộng \(Q\) lần. Lời gọi thứ \(i\) tương ứng với bước \(3\) và bước \(4\) của lượt thứ \(i\):

• Tham số u là dãy \(u_i\) do thiết bị gửi cho Bruno.
• Giá trị trả về là số nguyên Bruno gửi cho D-taro.
• Nếu giá trị trả về khác \(A_i\), chương trình bị chấm Wrong Answer [5].

Lưu ý quan trọng

• Bạn có thể cài đặt thêm hàm dùng nội bộ hoặc khai báo biến toàn cục. Hai tệp nộp sẽ được liên kết với chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ cần nằm trong namespace không tên để tránh xung đột với các tệp khác. Khi chấm thực tế, chương trình chạy dưới dạng hai tiến trình riêng cho Anna và Bruno; hai tiến trình không thể dùng chung biến toàn cục.
• Chương trình của bạn không được dùng đầu vào chuẩn, đầu ra chuẩn, hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Bạn được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Gói tệp phát kèm trên trang cuộc thi chứa chương trình chấm mẫu và các tệp chương trình mẫu. Chương trình chấm mẫu nằm trong grader.cpp. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng một thư mục và biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo. Chương trình chấm thực tế khác chương trình chấm mẫu. Chương trình chấm mẫu chỉ chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

Q
A_1
A_2
...
A_Q

Dữ liệu ra

Chương trình chấm mẫu ghi các thông tin sau ra đầu ra chuẩn:

• Nếu chương trình được chấm đúng, ghi giá trị \(m\) trả về bởi Declare, chẳng hạn Accepted: 2000.
• Nếu chương trình bị chấm sai, ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều loại lỗi, chương trình chấm mẫu chỉ thông báo một trong số đó.

Trong chương trình chấm mẫu, phép trộn ở mỗi lượt được chọn bằng bộ sinh số giả ngẫu nhiên. Kết quả không đổi giữa các lần chạy có cùng hạt giống. Có thể thay hạt giống bằng cách truyền một số nguyên làm đối số thứ nhất, chẳng hạn:

./grader 2022

Ràng buộc

• \(1\le Q\le1000\).
• \(1\le A_i\le10^{18}\) với mọi \(1\le i\le Q\).

Phân nhóm

• Nhóm 1 (5 điểm): \(A_i\le2000\) với mọi \(1\le i\le Q\).
• Nhóm 2 (5 điểm): \(A_i\le4000000\) với mọi \(1\le i\le Q\).
• Nhóm 3 (3 điểm): \(A_i\le10^7\) với mọi \(1\le i\le Q\).
• Nhóm 4 (12 điểm): \(A_i\le10^8\) với mọi \(1\le i\le Q\).
• Nhóm 5 (15 điểm): \(A_i\le10^{11}\) với mọi \(1\le i\le Q\).
• Nhóm 6 (60 điểm): Không có ràng buộc bổ sung. Điểm của nhóm được tính theo bảng dưới đây.

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 của nhóm 6. Lưu ý đây là giá trị công bố, không phải độ dài lớn nhất thực tế của các dãy được trả về.

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

2
42
2000

Lời gọi hàm

Giải thích

Ví dụ có \(Q=2\) lượt. Ở lượt 1, D-taro đưa \(A_1=42\) cho Anna; ở lượt 2, D-taro đưa \(A_2=2000\) cho Anna.

Ví dụ này thỏa mãn các nhóm \(1,2,3,4,5,6\) .

Nguồn

JOI 2021/2022, kỳ thi tuyển chọn mùa xuân, ngày thi thứ ba (22/03/2022). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.