Đây là bài chỉ xuất kết quả (output-only).

Khi cài đặt một mạch cho robot, bạn phát hiện một số bất thường. Robot có thể chạy \(N=128\) chương trình, đánh số từ \(0\) đến \(N-1\). Bình thường, tại mỗi thời điểm chỉ có đúng một chương trình chạy. Tuy nhiên, đôi khi có đúng ba chương trình chạy đồng thời. Bạn cần xây dựng một mạch để phát hiện tình huống bất thường này.

Ban đầu có \(N\) đầu vào. Đầu vào thứ \(i\) bằng \(0\) nếu chương trình thứ \(i\) không chạy, và bằng \(1\) nếu chương trình đó đang chạy. Sau đó, bạn thêm các cổng logic được đánh số liên tiếp bắt đầu từ \(N\). Mỗi cổng nhận một hoặc hai đầu vào và tạo ra một giá trị \(0\) hoặc \(1\). Đầu vào của cổng có chỉ số \(i\) có thể là một trong \(N\) đầu vào ban đầu hoặc đầu ra của một cổng có chỉ số nhỏ hơn \(i\).

Có ba loại cổng:

• NOT: nhận đúng một đầu vào; đầu ra bằng \(1\) khi đầu vào bằng \(0\), và ngược lại.
• OR: nhận đúng hai đầu vào; đầu ra bằng \(0\) khi cả hai đầu vào đều bằng \(0\), và bằng \(1\) trong các trường hợp còn lại.
• AND: nhận đúng hai đầu vào; đầu ra bằng \(1\) khi cả hai đầu vào đều bằng \(1\), và bằng \(0\) trong các trường hợp còn lại.

Đầu ra của cổng cuối cùng phải bằng \(1\) nếu có đúng ba trong \(N\) đầu vào ban đầu bằng \(1\), và bằng \(0\) nếu có đúng một đầu vào ban đầu bằng \(1\).

Dữ liệu luôn đảm bảo số đầu vào ban đầu bằng \(1\) là đúng một hoặc đúng ba.

Dữ liệu ra

Bạn phải tạo tệp 1.out mô tả một mạch hợp lệ cho \(N=128\).

Dòng đầu chứa số nguyên \(K\), là số cổng được sử dụng. Mỗi dòng trong \(K\) dòng tiếp theo có một trong ba dạng:

NOT in_1
OR in_1 in_2
AND in_1 in_2

Các dòng lần lượt thêm một cổng NOT, OR hoặc AND. Với NOT, in_1 là chỉ số đầu vào của cổng. Với OR và AND, in_1, in_2 là chỉ số hai đầu vào của cổng.

Cổng được mô tả ở dòng thứ \(i\) sau dòng đầu tiên có chỉ số

Nói cách khác, \(N\) đầu vào ban đầu có chỉ số từ \(0\) đến \(N-1\), cổng đầu tiên có chỉ số \(N\), và mọi chỉ số đầu vào được nhắc đến trên một dòng phải nhỏ hơn chỉ số cổng của dòng đó.

Tổng số cổng không được vượt quá \(1024\), tức là tệp kết quả có không quá \(1025\) dòng.

Chấm điểm

Bài có một phần trị giá \(100\) điểm và không có giới hạn thêm.

Nếu tồn tại một trạng thái đầu vào hợp lệ mà mạch cho kết quả sai, bài làm nhận \(0\) điểm. Ngược lại, với \(K\) là số cổng, điểm nhận được bằng \(100f(K)\), trong đó

Ví dụ

Xét phiên bản đơn giản với \(N=4\); bạn chỉ cần nộp lời giải cho \(N=128\). Một mạch hợp lệ là:

3
OR 0 1
OR 2 3
AND 4 5

Mạch gồm:

• Cổng \(4\) cho đầu ra \(1\) nếu ít nhất một trong hai đầu vào \(0,1\) bằng \(1\).
• Cổng \(5\) cho đầu ra \(1\) nếu ít nhất một trong hai đầu vào \(2,3\) bằng \(1\).
• Cổng \(6\) cho đầu ra \(1\) nếu đầu ra của cả cổng \(4\) và cổng \(5\) đều bằng \(1\).

Có thể kiểm tra rằng mạch cho kết quả đúng với mọi trạng thái đầu vào hợp lệ của phiên bản này.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Triple Circuit.