Anna và Bruno là các nhà khảo cổ học. Họ đang khảo sát các di tích ở Iran.
Công việc của họ như sau: Anna đến các di tích và tìm kiếm hiện 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 của họ dự kiến kéo dài $Q$ ($=1\,000$) ngày. Mỗi ngày, Anna gửi kết quả cho Bruno bằng một thiết bị liên lạc. Kết quả của mỗi ngày được biểu diễn bằng một số nguyên $X$.
Anna chỉ có thể dùng thiết bị liên lạc một lần mỗi ngày. Thiết bị có thể gửi một dãy độ dài $N$ ($=150$), gồm các giá trị $0$ hoặc $1$.
Tuy nhiên, thiết bị đã bị hỏng. Trong dãy độ dài $N$ có một số vị trí bị hỏng. Tại vị trí bị hỏng, thiết bị luôn gửi giá trị $0$, bất kể giá trị thực tế được đặt là gì. Khi gửi một dãy, Anna có thể biết các vị trí bị hỏng, nhưng Bruno không biết chúng. Các vị trí bị hỏng và số lượng vị trí bị hỏng có thể thay đổi mỗi ngày.
Cuộc khảo sát của họ có nguy cơ bị chậm trễ. Vì bạn là ứng viên tham dự một cuộc thi lập trình quốc tế ở Iran, Anna và Bruno nhờ bạn viết chương trình để gửi kết quả khảo sát của họ.
Yêu cầu
Hãy viết hai chương trình thực hiện việc liên lạc giữa Anna và Bruno.
- Cho độ dài dãy $N$, số nguyên cần gửi $X$, số vị trí bị hỏng $K$ và các vị trí bị hỏng $P$, chương trình thứ nhất thiết lập dãy $S$ do Anna gửi.
- Cho dãy $A$ mà Bruno nhận được, chương trình thứ hai khôi phục số nguyên $X$.
Tại vị trí mà thiết bị liên lạc hoạt động bình thường, dãy $S$ và dãy $A$ có cùng giá trị. Tại vị trí bị hỏng, dãy $A$ luôn có giá trị $0$, bất kể giá trị trong dãy $S$.
Chi tiết cài đặt
Bạn cần nộp hai tệp được viết bằng cùng một ngôn ngữ lập trình.
Tệp thứ nhất là Anna.c hoặc Anna.cpp. Tệp này thiết lập dãy do Anna gửi và cài đặt hàm sau. Chương trình phải bao gồm Annalib.h.
void Anna( int N, long long X, int K, int P[] )
Với mỗi bộ kiểm thử, hàm này được gọi $Q=1\,000$ lần.
- Tham số
Nlà độ dài của dãy cần gửi. - Tham số
Xlà số nguyên cần gửi. - Tham số
Klà số vị trí bị hỏng. - Tham số
P[]là một dãy độ dài $K$, mô tả các vị trí bị hỏng.
Trong hàm Anna, phải gọi hàm sau.
void Set( int pos, int bit )
Hàm này đặt một bit trong dãy $S$ cần gửi bằng thiết bị liên lạc.
- Tham số
poslà vị trí cần đặt.posphải là số nguyên từ $0$ đến $N-1$, kể cả hai đầu. Lưu ý rằng các vị trí được đánh số từ $0$. Nếu gọi hàm với tham số ngoài khoảng này, chương trình của bạn bị coi là trả lời saiWrong Answer[1]. Không được gọi hàm này nhiều hơn một lần với cùng tham sốpos. Nếu gọi hàm nhiều hơn một lần với cùng tham số, chương trình của bạn bị coi là trả lời saiWrong Answer[2]. - Tham số
bitlà giá trị được đặt tại vị trípostrong dãy. Giá trị củabitphải là $0$ hoặc $1$. Nếu gọi hàm với tham số khác, chương trình của bạn bị coi là trả lời saiWrong Answer[3].
Phải gọi Set đúng $N$ lần trong hàm Anna. Khi hàm Anna kết thúc, nếu số lần gọi Set khác $N$, chương trình của bạn bị coi là trả lời sai Wrong Answer[4].
Chương trình của bạn bị kết thúc nếu lời gọi hàm do Anna thực hiện bị coi là không hợp lệ.
Tệp thứ hai là Bruno.c hoặc Bruno.cpp. Tệp này khôi phục số nguyên biểu diễn kết quả khảo sát và cài đặt hàm sau. Chương trình phải bao gồm Brunolib.h.
long long Bruno( int N, int A[] )
Với mỗi bộ kiểm thử, hàm này được gọi $Q=1\,000$ lần.
- Tham số
Nlà độ dài của dãy mà Bruno nhận được. - Tham số
Alà một dãy số nguyên độ dài $N$. Đây là dãy mà Bruno nhận được. - Hàm
Brunophải khôi phục và trả về giá trị của $X$.
Quy trình chấm
Việc chấm được thực hiện như sau. Nếu chương trình của bạn bị coi là trả lời sai, chương trình bị kết thúc ngay lập tức.
- Đặt $\mathrm{cnt}=0$.
- Gọi hàm
Annamột lần. - Gọi $S$ là dãy được hàm
Annathiết lập. Trong dãy $S$, đặt giá trị $0$ tại các vị trí trong $P$ để thu được dãy $A$. Gọi hàmBrunomột lần với tham số $A$. - Đặt $\mathrm{cnt}=\mathrm{cnt}+1$. Nếu $\mathrm{cnt}<Q$, quay lại (2). Nếu $\mathrm{cnt}=Q$, chuyển đến (5).
- Chương trình của bạn được tính điểm.
Lưu ý quan trọng
- Thời gian chạy và bộ nhớ sử dụng được tính cho (1), (2), (3), (4) trong Quy trình chấm.
- Chương trình của bạn không được bị coi là trả lời sai trong lời gọi
Annaở (2) hoặcBrunoở (3). Chương trình phải chạy mà không gặp lỗi thực thi. - Chương trình có thể cài đặt thêm các hàm dùng nội bộ hoặc dùng biến toàn cục. Các chương trình được nộp sẽ được biên dịch cùng trình chấm, tạo thành một tệp thực thi. Tất cả biến toàn cục và hàm nội bộ phải được khai báo
staticđể tránh xung đột với các tệp khác. Vì chương trình của Anna và Bruno chạy dưới dạng 2 tiến trình riêng biệt khi chấm, chúng không thể dùng chung biến toàn cục. - Trong tiến trình, mỗi hàm
AnnavàBrunođược gọi $Q=1\,000$ lần. Các biến mà chương trình sử dụng phải được khởi tạo thích hợp. - Chương trình không được dùng đầu vào chuẩn và đầu ra chuẩn. Chương trình không được giao tiếp với các tệp khác bằng bất kỳ cách nào.
Biên dịch và chạy thử
Bạn có thể tải một tệp nén từ trang web cuộc thi, trong đó có trình chấm mẫu để kiểm thử chương trì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 gồm một tệp mã nguồn là grader.c hoặc grader.cpp. Ví dụ, nếu các chương trình của bạn là Anna.c và Bruno.c, hoặc Anna.cpp và Bruno.cpp, hãy chạy các lệnh sau để biên dịch.
- C
gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm
- C++
g++ -std=c++14 -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 duy nhất, đọ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 cho trình chấm mẫu
Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.
- Dòng đầu chứa một số nguyên $Q$.
- Tiếp theo là thông tin của $Q$ truy vấn.
Thông tin của mỗi truy vấn gồm hai dòng như sau.
- Dòng thứ nhất chứa ba số nguyên $N,X,K$ cách nhau bởi dấu cách. Điều này có nghĩa là độ dài dãy cần gửi là $N$, số nguyên Anna cần gửi là $X$ và có $K$ vị trí bị hỏng.
- Dòng thứ hai chứa $K$ số nguyên $P_0,P_1,\ldots,P_{K-1}$ cách nhau bởi dấu cách. Điều này có nghĩa là với mỗi $i$ ($0\le i\le K-1$), vị trí thứ $P_i$ trong dãy bị hỏng.
Dữ liệu ra của trình chấm mẫu
Khi chương trình kết thúc thành công, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn. (Dấu ngoặc kép không thực sự được ghi ra.)
- Nếu chương trình của bạn bị coi là trả lời sai, trình chấm mẫu ghi loại lỗi theo dạng
Wrong Answer [1], và chương trình của bạn bị kết thúc. - Nếu mọi lời gọi hàm
Annađều không bị coi là trả lời sai, trình chấm mẫu ghiAcceptedvà giá trị $L^*$. Về giá trị $L^*$, xem phần Nhiệm vụ con.
Nếu chương trình của bạn bị coi là nhiều loại trả lời sai, trình chấm mẫu chỉ báo một loại trong số đó.
Giới hạn
Mọi dữ liệu đầu vào đều thỏa mãn các điều kiện sau.
- $Q=1000$.
- $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$ ($0\le i\le K-1$).
- $P_i<P_{i+1}$ ($0\le i\le K-2$).
Nhiệm vụ con
Gọi $L^*$ là giá trị nhỏ nhất của đại lượng sau trên tất cả các bộ kiểm thử của bài này.
- Số nguyên lớn nhất $L\le 40$ sao cho với mọi truy vấn có $K\le L$, Bruno trả lời đúng giá trị $X$.
Điểm của bài được tính như sau:
- Nếu $L^*=0$, được 0 điểm.
- Nếu $1\le L^*\le14$, được 8 điểm.
- Nếu $15\le L^*\le37$, được $(L^*-15)\times2+41$ điểm.
- Nếu $38\le L^*\le40$, được $(L^*-38)\times5+90$ điểm.
Ví dụ giao tiếp
Dưới đây là một đầu vào mẫu cho trình chấm và các lời gọi hàm tương ứng. Lưu ý rằng ví dụ sau không thỏa mãn giới hạn của bài vì $Q=2,N=3$.
Dữ liệu vào 1
2 3 14 1 2 3 9 2 0 1
Các lời gọi mẫu
| Gọi | Trả về | Gọi | Trả về |
|---|---|---|---|
Anna(...) |
|||
Set(0,0) |
|||
| (không có) | |||
Set(1,0) |
|||
| (không có) | |||
Set(2,1) |
|||
| (không có) | |||
| (không có) | |||
Bruno(...) |
|||
14 |
|||
Anna(...) |
|||
Set(0,0) |
|||
| (không có) | |||
Set(1,1) |
|||
| (không có) | |||
Set(2,1) |
|||
| (không có) | |||
Bruno(...) |
|||
9 |
Các tham số của Anna(...), Bruno(...), Anna(...), Bruno(...) ở đây như sau.
| Tham số | Anna(...) |
Bruno(...) |
Anna(...) |
Bruno(...) |
|---|---|---|---|---|
N |
3 |
3 |
3 |
3 |
X |
14 |
9 |
||
K |
1 |
2 |
||
P |
{2} |
{0, 1} |
||
A |
{0, 0, 0} |
{0, 0, 1} |