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] Banker's algorithm - tìm chuỗi an toàn

    Tìm chuỗi an toàn (safe sequence) theo thuật toán Banker.

    Giống bài kiểm tra an toàn, nhưng in ra thứ tự ID tiến trình trong chuỗi an toàn. Để chuỗi xác định duy nhất: tại mỗi bước luôn chọn tiến trình có ID nhỏ nhất trong số các tiến trình chưa xong và thoả Need ≤ Work.

    Thuật toán: như Banker an toàn; mỗi lần "giải phóng" một tiến trình thì thêm ID nó vào chuỗi. Nếu cuối cùng đủ n tiến trình → in chuỗi (các ID cách nhau dấu cách); nếu không → in UNSAFE.

    Ví dụ: dữ liệu kinh điển n=5,m=3 → chuỗi 1 3 0 2 4.

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

      Dòng 1: n m. n dòng Allocation, n dòng Max, dòng cuối m số Available.

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

      1 ≤ n ≤ 200; 1 ≤ m ≤ 50; 0 ≤ giá trị ≤ 100000.

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

      Chuỗi ID tiến trình (0-based) cách nhau dấu cách, hoặc UNSAFE.

    Ví dụ:

    Đầu vào:

    5 3
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
3 3 2

    Đầu ra:

    1 3 0 2 4

    Giải thích:

    Available=[3,3,2]. Chọn ID nhỏ nhất thoả: P1(Need[1,2,2])→Work[5,3,2]. P3(Need[0,1,1])→[7,4,3]. P0(Need[7,4,3])→[7,5,3]. P2(Need[6,0,0])→[10,5,5]. P4(Need[4,3,1])→xong. Chuỗi: 1 3 0 2 4.

    Đang tải editor...