Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Dấu vết cấu hình: ô khác trắng và bề rộng đã dùng

    Dấu vết cấu hình: ô khác trắng và bề rộng đã dùng

    Cho máy Turing xác định. Chạy tới khi dừng (hết luật), tối đa limit bước. Khi dừng, hãy báo cáo hai đại lượng của dấu vết tính toán:

    1. Số ô khác trắng còn lại trên băng.
    2. Bề rộng vùng băng đã ghé thăm — số ô phân biệt mà đầu đọc từng đứng lên (tính cả ô bắt đầu 0, chính là ô_phải_nhất − ô_trái_nhất + 1 trong hành trình đầu đọc, đây là space complexity của lần chạy).

    Nếu không dừng trong limit bước: in LOOP.

    Ví dụ: máy ghi X tại 2 ô rồi dừng, đầu đọc đi qua các ô 0..2 → in 2 3.

    • Định dạng đầu vào:

      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.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 50; 1 ≤ limit ≤ 100000; độ dài băng ≤ 100.

    • Định dạng đầu ra:

      <số_ô_khác_trắng> <bề_rộng_đã_ghé_thăm>, hoặc LOOP.

    Ví dụ:

    Đầu vào:

    2
q0 _ q0 X R
q0 X q1 X R
q0
100
_X

    Đầu ra:

    2 3

    Giải thích:

    Ô 0 (`_`) ghi `X` sang phải; ô 1 (`X`) chuyển q1 sang phải; ô 2 (`_`) không có luật q1 → dừng. Băng có `X` ở ô 0,1 (2 ô khác trắng); đầu đọc ghé ô 0,1,2 (bề rộng 3) → `2 3`.

    Đang tải editor...