Bitaro và Bibako là hai nhà khảo cổ khai quật và nghiên cứu tàn tích của Vương quốc JOI. Trong tàn tích, Bitaro tìm thấy một phiến đá cổ, còn Bibako tìm thấy một cỗ máy cổ.

Qua nghiên cứu, Bitaro biết rằng trên phiến đá có một xâu \(S\) độ dài \(N\), mỗi ký tự là 0 hoặc 1. Tuy nhiên, anh chưa biết các ký tự của \(S\).

Bibako đã tìm ra cách sử dụng cỗ máy. Để đặt một câu hỏi, họ đặt phiến đá lên máy và nhập một số nguyên \(m\) cùng hai dãy số nguyên \(a,b\), thỏa mãn:

• \(1 \le m \le 1002\).
• Cả hai dãy \(a,b\) đều có độ dài \(m\).
• Mỗi phần tử của \(a,b\) nằm trong đoạn từ \(0\) đến \(m-1\).

Máy xử lý một câu hỏi và hiển thị một số nguyên như sau:

1. Máy đặt giá trị \(0\) vào vùng nhớ.
2. Máy thực hiện \(N\) thao tác. Ở thao tác thứ \(i+1\) (\(0 \le i \le N-1\)), gọi \(x\) là giá trị hiện tại trong vùng nhớ. Máy đọc ký tự \(S_i\), với các ký tự của \(S\) được đánh số từ \(0\). Nếu \(S_i\) là 0, máy thay giá trị trong vùng nhớ bằng \(a_x\); nếu \(S_i\) là 1, máy thay giá trị đó bằng \(b_x\). Các phần tử của \(a,b\) cũng được đánh số từ \(0\).
3. Máy hiển thị giá trị cuối cùng trong vùng nhớ.

Bitaro muốn dùng máy để xác định xâu trên phiến đá. Vì máy rất dễ hỏng, số câu hỏi không được vượt quá \(1000\). Ngoài ra, giá trị lớn nhất của \(m\) trong các câu hỏi cần nhỏ nhất có thể.

Hãy viết chương trình dùng cỗ máy để xác định xâu trên phiến đá.

Chi tiết cài đặt

Bạn cần nộp một tệp ancient2.cpp, dùng chỉ thị #include để khai báo tệp ancient2.h, và cài đặt hàm:

std::string Solve(int N);

Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử. Tham số N là độ dài của xâu \(S\) trên phiến đá. Hàm phải trả về chính xâu \(S\):

• Xâu trả về phải có độ dài \(N\). Nếu không, chương trình bị chấm Wrong Answer [1].
• Mỗi ký tự của xâu trả về phải là 0 hoặc 1. Nếu không, chương trình bị chấm Wrong Answer [2].
• Xâu trả về phải trùng với \(S\). Nếu không, chương trình bị chấm Wrong Answer [3].

Chương trình có thể gọi hàm sau để đặt câu hỏi:

int Query(int m, std::vector<int> a, std::vector<int> b);

m, a, b là số nguyên và hai dãy được nhập vào máy. Hàm trả về số nguyên mà máy hiển thị sau khi đặt phiến đá lên máy và xử lý câu hỏi với các tham số này.

• m phải nằm trong đoạn từ \(1\) đến \(1002\). Nếu không, chương trình bị chấm Wrong Answer [4].
• Độ dài của cả a và b phải bằng m. Nếu không, chương trình bị chấm Wrong Answer [5].
• Mỗi phần tử của a và b phải nằm trong đoạn từ \(0\) đến \(m-1\). Nếu không, chương trình bị chấm Wrong Answer [6].
• Không được gọi Query quá \(1000\) lần. Nếu vượt quá, chương trình bị chấm Wrong Answer [7].

Bạn có thể cài đặt các hàm phụ và sử dụng biến toàn cục. Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn, hay giao tiếp với tệp khác bằng bất kỳ cách nào. Tuy nhiên, có thể 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 hỗ trợ được đề gốc cung cấp qua trang kỳ thi chứa chương trình chấm mẫu và mã nguồn mẫu của chương trình cần nộp. Chương trình chấm mẫu là grader.cpp. Để thử chương trình, đặt grader.cpp, ancient2.cpp, ancient2.h trong cùng một thư mục và biên dịch bằng lệnh sau, hoặc chạy compile.sh trong gói hỗ trợ:

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

Sau khi biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm thật khác chương trình chấm mẫu. Chương trình chấm mẫu 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 từ đầu vào chuẩn theo định dạng:

N
S

Dữ liệu ra

Chương trình chấm mẫu ghi ra đầu ra chuẩn:

• Nếu chương trình trả lời đúng, ghi giá trị lớn nhất của tham số m trong các lần gọi Query, chẳng hạn Accepted: 22. Nếu trả lời đúng mà không gọi Query, ghi Accepted: 0.
• Nếu chương trình bị chấm Wrong Answer, ghi loại lỗi, chẳng hạn Wrong Answer [4].

Nếu chương trình vi phạm nhiều loại lỗi Wrong Answer, chương trình chấm mẫu chỉ báo một loại.

Ràng buộc

• \(N = 1000\).
• \(S\) là xâu độ dài \(N\).
• Mỗi ký tự của \(S\) là 0 hoặc 1.

Trong mỗi bộ kiểm thử, chương trình chấm thật không thích nghi: đáp án đã được cố định ngay từ đầu.

Phân nhóm

Nếu chương trình bị chấm Wrong Answer ở bất kỳ bộ kiểm thử nào, điểm của toàn bộ bài là \(0\).

Nếu chương trình trả lời đúng ở tất cả các bộ kiểm thử, gọi \(M\) là giá trị lớn nhất của tham số m trong mọi lần gọi Query trên tất cả các bộ kiểm thử. Nếu chương trình trả lời đúng mà không gọi Query trong bất kỳ bộ kiểm thử nào, đặt \(M=0\).

• Nếu \(103 \le M \le 1002\), điểm của bài là \(10+\left\lfloor\dfrac{(1002-M)^2}{9000}\right\rfloor\).
• Nếu \(0 \le M \le 102\), điểm của bài là \(100\).

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Ví dụ 1

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

3
110

Giải thích

Bảng sau minh họa các lời gọi hàm tương ứng với đầu vào của chương trình chấm mẫu:

Giả sử xâu trên phiến đá là 110. Khi nhập \((m,a,b)=(4,[3,3,2,2],[2,2,1,0])\), máy hoạt động như sau:

1. Đặt \(0\) vào vùng nhớ.
2. Ở thao tác đầu tiên, \(S_0\) là 1, nên đặt \(b_0=2\) vào vùng nhớ.
3. Ở thao tác thứ hai, \(S_1\) là 1, nên đặt \(b_2=1\) vào vùng nhớ.
4. Ở thao tác thứ ba, \(S_2\) là 0, nên đặt \(a_1=3\) vào vùng nhớ.
5. Giá trị cuối cùng trong vùng nhớ là \(3\), nên máy hiển thị \(3\).

Lưu ý rằng ví dụ này không thỏa mãn ràng buộc \(N=1000\). Trong các tệp mà đề gốc cung cấp qua trang kỳ thi, sample-02.txt thỏa mãn ràng buộc đó.

Nguồn

JOI Open Contest 2023 - Ancient Machine 2. Tác giả: Tomohito Hoshii. Đơn vị công bố: JCIOI (Ủy ban Nhật Bản về Olympic Tin học Quốc tế). Giấy phép: CC BY-SA 4.0.