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

    solution

    Đề bài: [Hệ điều hành] Readers-Writers — đếm thao tác bị chặn

    Mô phỏng bài toán Người đọc - Người ghi (Readers-Writers) với quy tắc:

    • Nhiều người đọc có thể đọc đồng thời.
    • Người ghi cần độc quyền: khi có người ghi đang ghi thì không ai khác (đọc hay ghi) vào được; khi đang có người đọc thì người ghi phải đợi.

    Cho dãy thao tác, mỗi thao tác một trong: RS (reader start), RE (reader end), WS (writer start), WE (writer end). Trạng thái duy trì: số người đọc đang đọc r, có người ghi đang ghi hay không w.

    Quy tắc thực hiện (greedy, không hàng đợi):

    • RS: cho phép nếu w = 0 (không có người ghi) → r += 1, thành công; ngược lại bị chặn (không đổi).
    • RE: nếu r > 0 → r −= 1 (thành công); ngược lại bỏ qua.
    • WS: cho phép nếu r = 0 và w = 0 → w = 1, thành công; ngược lại bị chặn.
    • WE: nếu w = 1 → w = 0 (thành công); ngược lại bỏ qua.

    In ra hai số cách nhau dấu cách: số thao tác bị chặn (RS hoặc WS không vào được), và số người đọc đang đọc ở cuối.

    Ví dụ: RS, RS, WS(bị chặn vì r=2), RE, RE, WS(ok). Bị chặn=1, r cuối=0.

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

      Dòng đầu: Q (số thao tác). Q dòng tiếp, mỗi dòng một mã thao tác: RS, RE, WS, WE.

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

      1 ≤ Q ≤ 100000.

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

      Hai số: số thao tác bị chặn, số người đọc đang đọc ở cuối.

    Ví dụ:

    Đầu vào:

    6
RS
RS
WS
RE
RE
WS

    Đầu ra:

    1 0

    Giải thích:

    RS->r=1; RS->r=2; WS bị chặn (r=2)->blocked=1; RE->r=1; RE->r=0; WS->w=1 (ok). Bị chặn=1, r cuối=0.

    Đang tải editor...