Một chip vi điều khiển có sẵn bộ nhớ flash gồm \(B\) bit. Ta cần lưu trữ và cập nhật một biến gồm \(M\) bit trong bộ nhớ này. Bộ nhớ flash có một hạn chế: có thể đổi riêng từng bit từ \(0\) thành \(1\), nhưng chỉ có thể đổi từ \(1\) thành \(0\) bằng cách xóa toàn bộ bộ nhớ. Bộ nhớ chỉ có thể được xóa một số lần hữu hạn trước khi chip bị hao mòn và phải thay thế. Vì vậy, ta muốn ghi được càng nhiều giá trị càng tốt trước khi phải xóa bộ nhớ.

Nhiệm vụ của bạn là thiết kế một cách lưu trữ hiệu quả sao cho luôn có thể khôi phục giá trị hiện tại. Cụ thể, chương trình của bạn phải thực hiện hai thao tác:

• Ghi một giá trị: đầu vào là trạng thái hiện tại của bộ nhớ và giá trị mới cần ghi; bạn phải đưa ra trạng thái mới của bộ nhớ.
• Đọc một giá trị: đầu vào là trạng thái của bộ nhớ sau một số thao tác ghi; bạn phải đưa ra giá trị được ghi trong thao tác ghi cuối cùng.

Hai thao tác đọc và ghi không được trao đổi thông tin bằng bất kỳ cách nào khác ngoài việc đọc trạng thái hiện tại của bộ nhớ từ đầu vào và, đối với thao tác ghi, đổi một số bit (có thể không đổi bit nào) từ \(0\) thành \(1\) trước khi đưa trạng thái mới ra đầu ra.

Yêu cầu nộp bài

Bạn cần nộp mã nguồn của một chương trình thực hiện cả hai vai trò đọc và ghi. Chương trình giao tiếp với hệ thống chấm qua đầu vào chuẩn và đầu ra chuẩn theo giao thức dưới đây; vai trò của mỗi lần chạy được xác định bởi giá trị \(T\) nhận được khi khởi động.

Giao thức tương tác

Đây là bài toán tương tác. Khi chương trình bắt đầu, dòng đầu tiên của đầu vào chứa số nguyên \(T\): \(T=0\) nghĩa là chương trình sẽ ghi các giá trị vào bộ nhớ, còn \(T=1\) nghĩa là chương trình sẽ đọc các giá trị từ bộ nhớ. Dòng thứ hai chứa hai số nguyên \(B\) và \(M\). Những dòng tiếp theo mô tả các thao tác.

Đối với cả hai vai trò, dòng đầu tiên của mỗi thao tác chứa số nguyên \(C\). Nếu \(C=0\), không còn yêu cầu nào và chương trình phải kết thúc. Nếu \(C=1\), chương trình phải tiếp tục xử lý:

• Nếu \(T=0\) và \(C=1\), dòng thứ hai của thao tác chứa hai xâu cách nhau bởi một dấu cách: trạng thái hiện tại của bộ nhớ dưới dạng xâu \(B\) bit và giá trị mới cần ghi dưới dạng xâu \(M\) bit. Nếu có thể ghi giá trị mới bằng cách chỉ đổi một số bit từ \(0\) thành \(1\), chương trình phải in số nguyên 1, rồi in trạng thái mới của bộ nhớ dưới dạng xâu \(B\) bit trên dòng tiếp theo. Nếu không thể ghi giá trị mới, chương trình phải in số nguyên 0.
• Nếu \(T=1\) và \(C=1\), dòng thứ hai của thao tác chứa một xâu duy nhất: trạng thái của bộ nhớ dưới dạng xâu \(B\) bit. Chương trình phải in một xâu \(M\) bit biểu diễn giá trị được ghi vào bộ nhớ gần nhất.

Sau mỗi câu trả lời, bạn phải đẩy hết bộ đệm đầu ra (flush) để bảo đảm hệ thống chấm nhận được câu trả lời. Đầu ra luôn phải kết thúc bằng ký tự xuống dòng. Các lệnh dưới đây minh họa việc trả lời một thao tác ghi thành công với trạng thái mới là s.

C:

fprintf(stdout, "1\n%s\n", s);
fflush(stdout);

C++:

cout << 1 << "\n" << s << endl;

Java:

System.out.println("1");
System.out.println(s);
System.out.flush();

Python:

sys.stdout.write("1\n{0}\n".format(s))
sys.stdout.flush()

Quá trình kiểm thử

Với mỗi test, hệ thống sẽ khởi chạy đồng thời bốn tiến trình của chương trình, gồm hai tiến trình ghi và hai tiến trình đọc. Giới hạn bộ nhớ và thời gian CPU được tính cho tổng cộng cả bốn tiến trình. Mọi hành vi cố ý truyền dữ liệu giữa các tiến trình qua kênh ngoài giao thức đều bị coi là gian lận và sẽ dẫn đến việc bị loại.

Ban đầu, hệ thống tạo một số khối bộ nhớ, mỗi khối gồm \(B\) bit đều bằng \(0\). Sau đó, các thao tác ghi và đọc được thực hiện theo một thứ tự hợp lệ nào đó.

Trong một thao tác ghi, một tiến trình ghi nhận trạng thái hiện tại của một khối cùng giá trị cần ghi vào khối đó. Bạn có thể giả sử các giá trị cần ghi được chọn ngẫu nhiên đều trong khoảng từ \(0\) đến \(2^M-1\), độc lập với mọi yếu tố khác. Nếu chương trình ghi được giá trị, trạng thái của khối được thay bằng trạng thái chương trình trả về. Nếu chương trình không ghi được giá trị, khối đó sẽ không tham gia bất kỳ thao tác ghi nào nữa.

Trong một thao tác đọc, một tiến trình đọc nhận trạng thái của một khối sau một thao tác ghi thành công. Hệ thống kiểm tra xem giá trị chương trình trả về có đúng là giá trị cần ghi trong thao tác ghi đó hay không. Đầu ra của mỗi thao tác ghi thành công được đọc đúng một lần.

Ràng buộc

Mọi test đều thỏa mãn \(N\cdot B\le 120\,000\), trong đó \(N\) là số thao tác ghi tối đa mà chương trình có thể được yêu cầu thực hiện. Các giá trị \(B\) và \(M\) của từng nhóm được liệt kê bên dưới.

Phân nhóm

Trong mỗi nhóm test, điểm của chương trình tỉ lệ với số giá trị trung bình ghi được trong các test thuộc nhóm. Cụ thể, nếu chương trình ghi được trung bình \(V\) giá trị trên mỗi khối, chương trình nhận được \(100\cdot V/P\%\) số điểm của nhóm, với \(P\) được cho dưới đây.

Nếu chương trình trả về giá trị sai trong bất kỳ thao tác đọc nào, điểm của toàn bộ nhóm bằng \(0\). Với bất kỳ lỗi nào khác, số giá trị đọc được trong test xảy ra lỗi được tính là \(0\).

1. Nhóm 1 (5 điểm): \(B=16\), \(M=8\), \(P=4.062445024495069624056\).
2. Nhóm 2 (5 điểm): \(B=32\), \(M=8\), \(P=12.264904841300964834177\).
3. Nhóm 3 (5 điểm): \(B=32\), \(M=16\), \(P=4.129591513707784802006\).
4. Nhóm 4 (5 điểm): \(B=64\), \(M=8\), \(P=30.039277894268828900030\).
5. Nhóm 5 (5 điểm): \(B=64\), \(M=16\), \(P=12.953148094217360432715\).
6. Nhóm 6 (5 điểm): \(B=64\), \(M=32\), \(P=4.073559788233661501537\).
7. Nhóm 7 (5 điểm): \(B=128\), \(M=8\), \(P=69.777892228928747548775\).
8. Nhóm 8 (5 điểm): \(B=128\), \(M=16\), \(P=34.731791275143635240976\).
9. Nhóm 9 (5 điểm): \(B=128\), \(M=32\), \(P=13.950788987705638908663\).
10. Nhóm 10 (5 điểm): \(B=128\), \(M=64\), \(P=4.039918210604800133907\).
11. Nhóm 11 (5 điểm): \(B=256\), \(M=8\), \(P=174.468047086071038511453\).
12. Nhóm 12 (5 điểm): \(B=256\), \(M=16\), \(P=82.222614151404177334554\).
13. Nhóm 13 (5 điểm): \(B=256\), \(M=32\), \(P=37.629382269769206488916\).
14. Nhóm 14 (5 điểm): \(B=256\), \(M=64\), \(P=14.263462282054140577686\).
15. Nhóm 15 (5 điểm): \(B=256\), \(M=128\), \(P=4.015569093893943430859\).
16. Nhóm 16 (5 điểm): \(B=512\), \(M=16\), \(P=204.746242127410346170221\).
17. Nhóm 17 (5 điểm): \(B=512\), \(M=32\), \(P=91.778595148073111539847\).
18. Nhóm 18 (5 điểm): \(B=512\), \(M=64\), \(P=39.230279242145938712621\).
19. Nhóm 19 (5 điểm): \(B=512\), \(M=128\), \(P=15.000000002167672268601\).
20. Nhóm 20 (5 điểm): \(B=512\), \(M=256\), \(P=4.005423277111055468876\).

Ví dụ

Input         Output
0
6 2
1
111111 00
              0
1
000000 11
              1
              110000
0

Input         Output
1
6 2
1
110000
              11
1
110100
              01
0

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.