JOI-kun đang chơi với một bộ mạch điện tử gồm \(N\) linh kiện AND, \(N\) linh kiện OR và một bảng mạch. Bảng mạch có \(2N+1\) công tắc và \(N\) khe cắm linh kiện; mỗi khe có thể được sử dụng bằng cách đặt vào đó một linh kiện AND hoặc OR. Bảng mạch cho ra giá trị \(0\) hoặc \(1\), tùy theo các linh kiện được đặt và trạng thái của các công tắc.

Quy tắc của bảng mạch

• Các công tắc được đánh số từ \(0\) đến \(2N\). Mỗi công tắc ở trạng thái ON (bật) hoặc OFF (tắt) và cho ra giá trị \(0\) hoặc \(1\) theo quy tắc dưới đây.
• Các khe cắm linh kiện được đánh số từ \(0\) đến \(N-1\). Mỗi khe cũng cho ra giá trị \(0\) hoặc \(1\).
• Giá trị của các công tắc và khe cắm được xác định theo thứ tự số hiệu giảm dần. Nếu một công tắc và một khe cắm có cùng số hiệu, giá trị của khe cắm được xác định trước.
• Với \(j=2N,2N-1,\ldots,N\), công tắc \(j\) cho ra \(0\) nếu ở trạng thái OFF và \(1\) nếu ở trạng thái ON.
• Với \(j=N-1,N-2,\ldots,0\), gọi \(x\) là giá trị của khe cắm \(j\). Công tắc \(j\) cho ra \(x\) nếu ở trạng thái OFF và \(1-x\) nếu ở trạng thái ON.
• Với \(i=N-1,N-2,\ldots,0\), khe cắm \(i\) nối với hai công tắc \(U_i,V_i\), trong đó \(i<U_i<V_i\le 2N\). Gọi \(x,y\) lần lượt là giá trị của hai công tắc này. Nếu khe cắm chứa linh kiện AND, nó cho ra \(\min(x,y)\); nếu chứa linh kiện OR, nó cho ra \(\max(x,y)\).
• Với mỗi \(j=1,2,\ldots,2N\), có đúng một chỉ số \(i\) (\(0\le i\le N-1\)) thỏa mãn \(U_i=j\) hoặc \(V_i=j\).
• Giá trị của bảng mạch bằng giá trị của công tắc \(0\).

Ví dụ, khi \(N=3\), \(U_0=1\), \(V_0=2\), \(U_1=3\), \(V_1=4\), \(U_2=5\), \(V_2=6\), các khe cắm \(0,1\) chứa linh kiện AND và khe cắm \(2\) chứa linh kiện OR, bảng mạch được biểu diễn như hình sau.

JOI-kun định đặt linh kiện AND vào tất cả các khe cắm, nhưng phát hiện có nhiều nhất \(R\) linh kiện OR bị đặt lẫn vào. Vì linh kiện AND và OR có hình dạng giống nhau, cần dùng bảng mạch để phân biệt chúng. Bạn được hỏi JOI-kun nhiều nhất \(1000\) truy vấn theo dạng sau:

• Chỉ định trạng thái của cả \(2N+1\) công tắc. JOI-kun sẽ đặt các công tắc theo yêu cầu và cho bạn biết giá trị của bảng mạch.

Cho cấu trúc kết nối và cận trên của số linh kiện OR, hãy xác định tất cả các khe cắm chứa linh kiện OR bằng nhiều nhất \(1000\) truy vấn.

Chi tiết cài đặt

Bạn cần nộp một tệp có tên circuit.cpp. Tệp này phải dùng chỉ thị #include để nạp circuit.h và cài đặt hàm sau:

std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)

• Hàm được gọi đúng một lần trong mỗi bộ dữ liệu.
• N là số khe cắm linh kiện; R là cận trên của số linh kiện OR.
• U và V là hai mảng độ dài \(N\). Với \(0\le i\le N-1\), U[i] và V[i] là số hiệu \(U_i,V_i\) của hai công tắc nối với khe cắm \(i\).
• Hàm phải trả về xâu \(t\) độ dài \(N\) chỉ gồm & và |. Với mỗi \(i=0,1,\ldots,N-1\), t[i] phải là & nếu khe cắm \(i\) chứa linh kiện AND và là | nếu chứa linh kiện OR.
• Nếu độ dài xâu trả về khác \(N\), chương trình bị chấm Wrong Answer [1].
• Nếu xâu trả về chứa ký tự khác & và |, chương trình bị chấm Wrong Answer [2].
• Nếu loại linh kiện thực tế tại một khe cắm khác loại được biểu diễn trong xâu trả về, chương trình bị chấm Wrong Answer [3].

Chương trình của bạn có thể gọi hàm sau:

int query(std::string s)

• Hàm này dùng để hỏi JOI-kun một truy vấn.
• s phải là xâu độ dài \(2N+1\) chỉ gồm 0 và 1. Với mỗi \(j=0,1,\ldots,2N\), s[j] bằng 0 nghĩa là đặt công tắc \(j\) ở trạng thái OFF, còn s[j] bằng 1 nghĩa là đặt ở trạng thái ON.
• Nếu độ dài của s khác \(2N+1\), chương trình bị chấm Wrong Answer [4].
• Nếu s chứa ký tự khác 0 và 1, chương trình bị chấm Wrong Answer [5].
• Không được gọi hàm quá \(1000\) lần. Nếu vượt quá giới hạn này, chương trình bị chấm Wrong Answer [6].
• Hàm trả về giá trị của bảng mạch sau khi đặt các công tắc theo s.

Lưu ý

Bạn được cài đặt thêm các hàm phụ và khai báo biến toàn cục để dùng nội bộ. Chương trình không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác. 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 được cung cấp trên trang cuộc thi chứa chương trình chấm mẫu và một tệp mã nguồn mẫu cho phần cần cài đặt. Chương trình chấm mẫu là tệp grader.cpp. Để chạy thử, đặt grader.cpp, circuit.cpp và circuit.h trong cùng một thư mục rồi dùng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp circuit.cpp

Bạn cũng có thể chạy tệp compile.sh có trong gói:

./compile.sh

Nếu biên dịch thành công, tệp thực thi grader sẽ đượ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ạ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

Gọi \(T\) là xâu độ dài \(N\) mà hàm solve cần trả về. Chương trình chấm mẫu đọc dữ liệu theo dạng:

N R
U_0 V_0
U_1 V_1
...
U_{N-1} V_{N-1}
T

Dữ liệu ra

• Nếu chương trình trả lời đúng, chương trình chấm mẫu in số lần gọi query, chẳng hạn Accepted: 22.
• Nếu chương trình bị chấm sai, chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [4].

Chương trình chấm mẫu kết thúc ngay khi gặp một điều kiện sai. Nếu có nhiều điều kiện sai, chỉ một loại lỗi được hiển thị.

Chương trình chấm thực tế không thích nghi: đáp án đã được cố định từ trước khi bắt đầu tương tác.

Ràng buộc

• \(1\le N\le 8000\).
• \(1\le R\le\min(N,120)\).
• \(i<U_i<V_i\le 2N\) (\(0\le i\le N-1\)).
• Với mỗi \(j=1,2,\ldots,2N\), có đúng một chỉ số \(i\) (\(0\le i\le N-1\)) thỏa mãn \(U_i=j\) hoặc \(V_i=j\).

Chấm điểm

1. \(1\) điểm: \(N=1\).
2. \(4\) điểm: \(N\le 1000\), \(R=1\).
3. \(5\) điểm: \(N\le 1000\).
4. \(17\) điểm: \(U_i=i+1\), \(V_i=N+1+i\) với mọi \(0\le i\le N-1\); \(R\le 70\).
5. \(8\) điểm: \(U_i=i+1\), \(V_i=N+1+i\) với mọi \(0\le i\le N-1\).
6. \(23\) điểm: \(U_i=2i+1\), \(V_i=2i+2\) với mọi \(0\le i\le N-1\); \(R\le 70\).
7. \(8\) điểm: \(U_i=2i+1\), \(V_i=2i+2\) với mọi \(0\le i\le N-1\).
8. \(27\) điểm: \(R\le 70\).
9. \(7\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là dữ liệu vào của chương trình chấm mẫu và các lời gọi hàm tương ứng.

Ví dụ 1

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

1 1
1 2
|

Tương tác

Chương trình chấm gọi solve(1, 1, [1], [2]).

Cuối cùng, solve trả về xâu |.

Giải thích

Trong lần gọi query đầu tiên:

• Công tắc \(1\) ở trạng thái ON và công tắc \(2\) ở trạng thái OFF, nên chúng lần lượt cho ra \(1\) và \(0\).
• Khe cắm \(0\) chứa linh kiện OR, hai công tắc nối với nó cho ra \(1\) và \(0\), nên khe cắm cho ra \(\max(1,0)=1\).
• Công tắc \(0\) ở trạng thái OFF và khe cắm \(0\) cho ra \(1\), nên công tắc \(0\) cho ra \(1\).
• Vì vậy, bảng mạch cho ra \(1\).

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 2

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

3 3
1 2
3 4
5 6
&&|

Tương tác

Chương trình chấm gọi solve(3, 3, [1, 3, 5], [2, 4, 6]).

Cuối cùng, solve trả về xâu &&|.

Giải thích

Hình trong đề bài biểu diễn bảng mạch của ví dụ này.

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,6,7,8,9\).

Trong các tệp được cung cấp trên trang cuộc thi, sample-01-in.txt tương ứng với ví dụ \(1\), sample-02-in.txt tương ứng với ví dụ \(2\). Ngoài ra, sample-03-in.txt thỏa mãn ràng buộc của các nhóm \(3,4,5,8,9\) và sample-04-in.txt thỏa mãn ràng buộc của các nhóm \(3,6,7,8,9\).

Nguồn

Bài Circuit 2, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt; hình minh họa được giữ lại từ đề chính thức.