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

Chủ tịch K chuẩn bị một trò chơi cho những người tham gia trại huấn luyện mùa xuân. Có \(N\) người tham gia, được đánh số từ \(1\) đến \(N\). Mỗi người có một tấm bảng. Trò chơi diễn ra như sau:

1. Chủ tịch K chọn một người làm người cha; tất cả những người còn lại là người con. Ông không thông báo cho những người tham gia ai được chọn làm người cha.
2. Chủ tịch K viết ký tự T lên bảng của người cha và ký tự F lên bảng của tất cả những người con.
3. Mỗi người đọc ký tự trên bảng của chính mình. Sau đó, mọi người thực hiện \(L\) lượt theo một chiến lược đã thống nhất trước.
4. Sau \(L\) lượt, mỗi người phải trả lời số hiệu của người cha.

Mỗi lượt trong bước \(3\) gồm hai giai đoạn theo thứ tự:

• Trước hết, mỗi người xóa ký tự trên bảng của mình, viết một ký tự mới là T hoặc F, rồi đưa bảng cho chủ tịch K.
• Sau đó, lần lượt với \(i=1,2,\ldots,N\), người \(i\) chọn một người có số hiệu \(p\) (\(1 \le p \le N\)) và báo số \(p\) cho chủ tịch K. Chủ tịch K cho người \(i\) xem bảng của người \(p\), và người \(i\) đọc ký tự trên bảng đó. Người \(i\) được phép chọn chính mình.

Mục tiêu là thống nhất trước một chiến lược sao cho, bất kể ai được chọn làm người cha, cuối cùng tất cả mọi người đều xác định đúng số hiệu người cha. Bạn muốn đạt mục tiêu với số lượt \(L\) càng nhỏ càng tốt.

Một chiến lược gồm số nguyên không âm \(L\) và các quy tắc quyết định hành động như sau:

• Với người \(i\) (\(1 \le i \le N\)), giả sử các ký tự người đó đã đọc trước khi lượt \(t\) (\(1 \le t \le L\)) bắt đầu lần lượt là \(a_0,a_1,\ldots,a_{t-1}\). Chỉ dựa trên thông tin \((i,t,a_0,a_1,\ldots,a_{t-1})\), người đó phải quyết định cả ký tự sẽ viết lên bảng trong lượt \(t\) lẫn số hiệu người sẽ chọn để xem bảng trong lượt đó.
• Với người \(i\), giả sử các ký tự đã đọc đến hết lượt \(L\) lần lượt là \(a_0,a_1,\ldots,a_L\). Chỉ dựa trên thông tin \((i,L,a_0,a_1,\ldots,a_L)\), người đó phải quyết định số hiệu người cha mà mình sẽ trả lời.

Ở đây, \(a_0\) là ký tự được đọc trên bảng của chính người đó trước lượt đầu tiên, còn \(a_t\) là ký tự đọc được trong lượt \(t\).

Hãy xây dựng một chiến lược đạt mục tiêu. Với từng trường hợp người cha là \(1,2,\ldots,N\), hãy xuất ký tự mà mỗi người viết lên bảng và số hiệu người mà họ chọn xem bảng ở mỗi lượt khi thực hiện cùng chiến lược đó.

Dữ liệu vào

Mỗi tệp dữ liệu vào chứa một số nguyên \(N\).

Dữ liệu ra

Xuất dữ liệu theo cấu trúc:

L
acts_1
acts_2
...
acts_N

Dòng đầu tiên chứa số nguyên không âm \(L\), là số lượt của chiến lược. Khối \(acts_s\) mô tả hành động của mọi người trong trường hợp người \(s\) là người cha. Các khối được xuất theo thứ tự \(s=1,2,\ldots,N\).

Mỗi khối \(acts_s\) có cấu trúc:

s
c_{1,1} p_{1,1} c_{1,2} p_{1,2} ... c_{1,L} p_{1,L}
c_{2,1} p_{2,1} c_{2,2} p_{2,2} ... c_{2,L} p_{2,L}
...
c_{N,1} p_{N,1} c_{N,2} p_{N,2} ... c_{N,L} p_{N,L}

• Dòng đầu tiên của khối chứa số nguyên \(s\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) mô tả hành động của người \(i\). Với mỗi lượt \(t=1,2,\ldots,L\), xuất lần lượt ký tự \(c_{i,t}\) mà người đó viết lên bảng và số hiệu \(p_{i,t}\) của người mà họ chọn xem bảng. Các giá trị trên một dòng được ngăn cách bởi dấu cách.
• \(c_{i,t}\) phải là T hoặc F, và \(1 \le p_{i,t} \le N\).

Điều kiện hợp lệ

Kết quả được coi là đúng khi và chỉ khi tồn tại một chiến lược đạt mục tiêu mà dữ liệu xuất ra chính là các hành động khi thực hiện chiến lược đó. Cụ thể, phải đồng thời thỏa mãn hai điều kiện:

1. Với mọi người \(i\) (\(1 \le i \le N\)), mọi lượt \(t\) (\(1 \le t \le L\)) và hai ứng viên người cha khác nhau \(x,y\) (\(1 \le x,y \le N\), \(x\ne y\)): nếu dãy ký tự mà người \(i\) đã đọc trước lượt \(t\) giống nhau trong trường hợp người cha là \(x\) và trường hợp người cha là \(y\), thì hành động của người \(i\) ở lượt \(t\) cũng phải giống nhau trong hai trường hợp, tức là viết cùng ký tự và chọn cùng một người để xem bảng.
2. Với mọi người \(i\) và hai ứng viên người cha khác nhau \(x,y\), dãy ký tự mà người \(i\) đã đọc đến hết lượt \(L\) trong trường hợp người cha là \(x\) phải khác dãy ký tự trong trường hợp người cha là \(y\).

Tệp kết quả

Chỉ nộp các tệp kết quả output_01.txt, output_02.txt, output_03.txt, lần lượt tương ứng với các tệp dữ liệu vào input_01.txt, input_02.txt, input_03.txt.

Ràng buộc

\(N\) là một trong ba giá trị \(4\), \(32\), \(48\).

Chấm điểm

Điểm của bài là tổng điểm của ba bộ dữ liệu vào. Với mỗi bộ dữ liệu, nếu kết quả sai định dạng hoặc không thỏa mãn các điều kiện hợp lệ, điểm của bộ dữ liệu đó bằng \(0\).

Nếu kết quả hợp lệ, điểm được tính theo số lượt \(L\) trong tệp kết quả tương ứng:

Nếu điểm bằng \(0\), hệ thống chấm của kỳ thi gốc hiển thị thông báo Output isn't correct, kể cả khi nguyên nhân là số lượt quá lớn.

Ví dụ

3

3
1
T 1 T 2 T 3
F 1 F 2 F 3
F 1 F 2 F 3
2
F 1 F 2 F 3
T 1 T 2 T 3
F 1 F 2 F 3
3
F 1 F 2 F 3
F 1 F 2 F 3
T 1 T 2 T 3

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.