Anna và Bruno là hai nhà khảo cổ đang khảo sát một khu di tích tại Iran. Anna đến di tích để tìm cổ vật, còn Bruno phân tích kết quả tại trại căn cứ.

Cuộc khảo sát kéo dài \(Q=1\,000\) ngày. Mỗi ngày, Anna gửi cho Bruno một kết quả được biểu diễn bởi số nguyên \(X\). Thiết bị liên lạc chỉ có thể được dùng một lần mỗi ngày và gửi một dãy nhị phân độ dài \(N=150\).

Thiết bị bị hỏng tại một số vị trí. Một vị trí hỏng luôn truyền giá trị \(0\), bất kể Anna đặt giá trị nào. Khi gửi, Anna biết số lượng và vị trí các chỗ hỏng, nhưng Bruno không biết. Tập vị trí hỏng có thể thay đổi mỗi ngày.

Yêu cầu

Viết hai chương trình cùng ngôn ngữ để thực hiện việc liên lạc:

• Chương trình của Anna nhận \(N,X,K\) và mảng vị trí hỏng \(P\), rồi thiết lập dãy \(S\) cần gửi.
• Chương trình của Bruno nhận dãy \(A\) mà thiết bị truyền đến và phải khôi phục \(X\).

Ở vị trí hoạt động bình thường, \(A\) bằng \(S\). Ở vị trí hỏng, \(A\) luôn bằng \(0\).

Chi tiết cài đặt

Bạn phải nộp hai tệp viết bằng cùng một ngôn ngữ.

Tệp thứ nhất là Anna.c hoặc Anna.cpp, phải khai báo #include "Annalib.h" và cài đặt hàm:

void Anna(int N, long long X, int K, int P[])

Trong mỗi bộ kiểm thử, hàm này được gọi \(Q=1\,000\) lần:

• \(N\) là độ dài dãy cần gửi.
• \(X\) là số nguyên cần gửi.
• \(K\) là số vị trí hỏng.
• P là mảng độ dài \(K\) chứa các vị trí hỏng.

Trong Anna, bạn phải gọi hàm sau:

void Set(int pos, int bit)

• pos là vị trí cần đặt và phải thuộc đoạn \([0,N-1]\). Gọi với vị trí ngoài đoạn này dẫn đến Wrong Answer [1]. Không được gọi hai lần với cùng một pos; vi phạm dẫn đến Wrong Answer [2].
• bit phải bằng \(0\) hoặc \(1\); giá trị khác dẫn đến Wrong Answer [3].
• Set phải được gọi đúng \(N\) lần trong mỗi lần gọi Anna. Số lần gọi khác \(N\) dẫn đến Wrong Answer [4].

Nếu một lời gọi của Anna không hợp lệ, chương trình sẽ bị dừng.

Tệp thứ hai là Bruno.c hoặc Bruno.cpp, phải khai báo #include "Brunolib.h" và cài đặt hàm:

long long Bruno(int N, int A[])

Trong mỗi bộ kiểm thử, hàm này được gọi \(Q=1\,000\) lần:

• \(N\) là độ dài dãy Bruno nhận được.
• A là mảng số nguyên độ dài \(N\) chứa dãy nhận được.
• Hàm phải khôi phục và trả về \(X\).

Quy trình chấm

Nếu chương trình bị xác định là sai, quá trình chấm dừng ngay lập tức.

1. Đặt cnt = 0.
2. Gọi Anna một lần.
3. Gọi \(S\) là dãy được Anna thiết lập. Đặt các vị trí thuộc \(P\) trong \(S\) thành \(0\) để thu được \(A\), rồi gọi Bruno với tham số \(A\).
4. Tăng cnt thêm \(1\). Nếu cnt < Q, quay lại bước 2; nếu cnt = Q, chuyển sang bước 5.
5. Tính điểm chương trình.

Thời gian và bộ nhớ được tính cho các bước 1 đến 4.

Các lời gọi Anna và Bruno không được gây lỗi thực thi. Bạn có thể cài đặt thêm hàm hoặc dùng biến toàn cục, nhưng mọi hàm và biến toàn cục nội bộ nên được khai báo static để tránh xung đột khi liên kết với bộ chấm. Khi chấm chính thức, chương trình của Anna và Bruno chạy trong hai tiến trình riêng biệt nên không thể chia sẻ biến toàn cục.

Trong mỗi tiến trình, hàm tương ứng được gọi \(Q=1\,000\) lần; các biến phải được khởi tạo phù hợp. Chương trình không được dùng đầu vào/đầu ra chuẩn hoặc giao tiếp với tệp theo bất kỳ cách nào.

Bộ chấm mẫu

Gói đính kèm của đề chứa bộ chấm mẫu và mã nguồn mẫu. Nếu hai tệp của bạn là Anna.c, Bruno.c hoặc Anna.cpp, Bruno.cpp, có thể biên dịch như sau:

gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm
g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Bộ chấm thật khác bộ chấm mẫu. Bộ chấm mẫu chạy trong 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 bộ chấm mẫu

• Dòng đầu chứa số nguyên \(Q\).
• Sau đó là thông tin của \(Q\) truy vấn, mỗi truy vấn gồm hai dòng:
• Dòng đầu gồm \(N,X,K\).
• Dòng thứ hai gồm \(K\) số \(P_0,P_1,\ldots,P_{K-1}\).

Dữ liệu ra của bộ chấm mẫu

• Nếu chương trình vi phạm một quy tắc, bộ chấm in loại lỗi theo dạng Wrong Answer [1] rồi dừng. Nếu có nhiều lỗi, chỉ một lỗi được báo.
• Nếu mọi lời gọi Anna đều hợp lệ, bộ chấm in Accepted cùng giá trị \(L^*\) được định nghĩa trong phần chấm điểm.

Ràng buộc

• \(Q=1\,000\).
• \(N=150\).
• \(0 \le X \le 1\,000\,000\,000\,000\,000\,000\).
• \(1 \le K \le 40\).
• \(0 \le P_i \le N-1\) với mọi \(0 \le i \le K-1\).
• \(P_i<P_{i+1}\) với mọi \(0 \le i \le K-2\).

Chấm điểm

Với mỗi bộ kiểm thử, xét số nguyên lớn nhất \(L \le 40\) sao cho Bruno trả lời đúng \(X\) cho mọi truy vấn có \(K \le L\). Gọi \(L^*\) là giá trị nhỏ nhất của \(L\) trên tất cả các bộ kiểm thử của bài.

Điểm số được tính như sau:

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.

Ví dụ giao tiếp

Ví dụ sau không thỏa mãn ràng buộc chính thức vì \(Q=2\) và \(N=3\).

2
3 14 1
2
3 9 2
0 1

Các lời gọi tương ứng:

Tài liệu gốc chỉ mô tả chuỗi lời gọi và giá trị trả về cho ví dụ giao tiếp này, không cho một dòng kết quả cụ thể của bộ chấm mẫu.