Máy "Busy Beaver" là máy Turing trên bảng chữ {0, 1} với ô trắng là 0, băng khởi tạo toàn 0. Máy có một trạng thái dừng đặc biệt (halt); khi vào trạng thái này máy dừng ngay.
Hãy mô phỏng máy (tối đa limit bước) và in ra số bước đã thực hiện và số dấu 1 còn lại trên băng khi dừng.
Ví dụ (BB-2 kinh điển):
A 0 -> B 1 R
A 1 -> B 1 L
B 0 -> A 1 L
B 1 -> H 1 R
Máy dừng sau 6 bước và để lại 4 dấu 1.
Dòng 1: n số luật.
n dòng: q a ns wr d (ký hiệu chỉ là 0 hoặc 1).
Dòng tiếp: start halt (trạng thái đầu và trạng thái dừng).
Dòng tiếp: số nguyên limit.
1 ≤ n ≤ 40; 1 ≤ limit ≤ 100000.
Hai số cách nhau khoảng trắng: số_bước số_dấu_1.
Ví dụ:
Đầu vào:
4
A 0 B 1 R
A 1 B 1 L
B 0 A 1 L
B 1 H 1 R
A H
1000
Đầu ra:
6 4
Giải thích:
Đang tải editor...