Tại Cesenatico có một hội kín gồm \(N\) nhà tin học nữ. Không thành viên nào biết thành viên nào khác. Mỗi thành viên có một ID duy nhất là số nguyên không âm \(I\).

Các thành viên chỉ giao tiếp gián tiếp bằng những con số viết phấn tại nhiều địa điểm trong thành phố. Cứ 100 năm, hội tiến hành điều tra dân số. Khi hoàn tất, mọi thành viên phải biết chính xác tổng số thành viên \(N\).

Quá trình kéo dài nhiều ngày. Trong mỗi ngày, mỗi thành viên chưa dừng phải chọn đúng một hành động:

• Đọc: chọn địa điểm \(P\), đến đó ban ngày và đọc số đang được viết.
• Ghi: chọn địa điểm \(P\) và số \(V\), đến đó vào tối muộn và thay số cũ bằng \(V\). Người ghi không được đọc số cũ trước khi ghi.
• Dừng: không thực hiện hành động nào trong các ngày sau.

Nghiêm cấm từ hai thành viên trở lên ghi vào cùng một địa điểm trong cùng ngày. Nhiều người có thể đọc cùng chỗ. Nếu trong cùng ngày có người đọc và người ghi cùng một chỗ, mọi lượt đọc xảy ra trước lượt ghi.

Hãy lập chiến lược làm giảm số ngày đến khi mọi thành viên biết đúng \(N\).

Giao thức tương tác

Đây là bài giao tiếp nhiều tiến trình. Có một số chưa biết \(N\) tiến trình submission chạy đồng thời, mỗi tiến trình đại diện cho một thành viên.

Có \(10^{18}\) địa điểm, đánh số \(0\le P<10^{18}\). Ban đầu mọi địa điểm chứa \(0\). Giá trị được ghi phải là số nguyên \(0\le V\le10^9\); trong hầu hết phân nhóm chỉ được ghi \(0\) hoặc \(1\).

Khi bắt đầu, mỗi tiến trình đọc hai số \(I,M\) (\(0\le I<M\)): ID riêng của thành viên và tổng số ID có thể có. Mọi tiến trình trong cùng test nhận cùng \(M\), nhận các \(I\) đôi một khác nhau, và có thể có ID không thuộc thành viên nào.

Mỗi ngày, tiến trình in đúng một trong các lệnh:

• r P: đọc địa điểm \(P\), sau đó đọc một dòng chứa giá trị hiện tại tại đó.
• w P V: ghi \(V\) tại \(P\). Nếu nhiều tiến trình ghi cùng \(P\) trong ngày, đáp án bị chấm sai.
• ! N: trả lời và dừng. Sau lệnh này, tiến trình phải kết thúc bình thường; các tiến trình khác có thể tiếp tục.

Nếu bất kỳ tiến trình nào trả lời sai, vi phạm giao thức, dùng quá \(500\) ngày hoặc vượt giới hạn thời gian/bộ nhớ riêng của tiến trình, test bị chấm sai. Nếu không, điểm test phụ thuộc vào \(D\), số ngày lớn nhất mà một tiến trình dùng. Để đạt trọn điểm cần \(D\le61\) và chỉ ghi \(V\in\{0,1\}\).

Sau mỗi lần in lệnh, phải flush standard output. Trong C++ có thể dùng cout << endl hoặc fflush(stdout); trong Python, input() tự flush luồng output đang chờ.

Ràng buộc

• \(1\le N\le100\).
• \(1\le M\le100\,000\).
• Được dùng tối đa \(500\) ngày.

Phân nhóm

1. \(11\) điểm: \(M\le100\) và các ID là \(0,1,\ldots,N-1\).
2. \(12\) điểm: \(N\le2\).
3. \(22\) điểm: \(M\le8000\) và được ghi mọi số \(0\le V\le10^9\).
4. \(55\) điểm: không có ràng buộc thêm.

Trong các nhóm 1, 2 và 4, chỉ được ghi \(V=0\) hoặc \(V=1\).

Gọi \(X_s\) là điểm tối đa của nhóm \(s\) và \(D_s\) là số ngày lớn nhất trên các test của nhóm đó. Điểm nhóm là:

Hình 1: Tổng điểm khi mọi phân nhóm đều được giải với cùng số ngày lớn nhất \(D\).

Kết quả được làm tròn đến số nguyên gần nhất theo từng nhóm.

Ví dụ giao thức

Ví dụ chính thức thứ nhất có \(N=5\), \(M=100\), các ID \(0,1,2,3,4\). Ví dụ thứ hai có \(N=2\), \(M=8000\), các ID \(0,3\). Các chuỗi lệnh trong đề gốc chỉ minh họa giao thức, không phải chiến lược hiệu quả. Trong ngày, lượt đọc luôn thấy giá trị trước các lượt ghi của chính ngày đó.

Công cụ thử nghiệm

Gói đính kèm cung cấp testing_tool.py, hai template census.cpp, census.py và hai input mẫu. Input cho công cụ gồm \(N,M\), sau đó là \(N\) ID. Công cụ này chỉ hỗ trợ thử cục bộ và không phải grader chính thức.

Nguồn

EGOI 2026 - Ngày 1, Census.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).