Cho máy Turing xác định (không có trạng thái chấp nhận đặc biệt — máy dừng khi không tồn tại luật cho cặp (trạng_thái, ký_hiệu_đọc) hiện tại).
Hãy đếm số bước máy thực hiện cho tới khi dừng.
Nếu sau limit bước máy vẫn chưa dừng, in -1 (coi như không dừng trong giới hạn).
Ví dụ: máy có duy nhất luật q0 a -> q0 a R, băng aa. Bước 1 đọc a (ô 0), bước 2 đọc a (ô 1), bước 3 đọc _ (ô 2) → không có luật → dừng. Số bước = 2.
Dòng 1: n số luật.
n dòng: q a ns wr d.
Dòng tiếp: start.
Dòng tiếp: số nguyên limit.
Dòng cuối: chuỗi băng đầu.
1 ≤ n ≤ 50; 1 ≤ limit ≤ 100000; độ dài băng ≤ 100.
In số bước tới khi dừng, hoặc -1 nếu chưa dừng sau limit bước.
Ví dụ:
Đầu vào:
1
q0 a q0 a R
q0
1000
aa
Đầu ra:
2
Giải thích:
Đang tải editor...