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] Free-space bitmap — đếm và first-fit

    Free-space Bitmap — đếm và cấp phát first-fit

    Đĩa quản lý không gian trống bằng bitmap: chuỗi n bit, 1 = block đã cấp, 0 = block trống.

    Thuật toán

    1. Đếm free_total = số bit 0.
    2. Tìm first-fit: vị trí bắt đầu của dãy 0 liên tiếp đầu tiên có độ dài ≥ need. Nếu không có → -1.

    In free_total rồi vị trí bắt đầu (chỉ số 0-based) hoặc -1.

    Ví dụ

    n=8, bitmap 11000110, need=2. Số bit 0 = 4. Dãy 0 liên tiếp: vị trí 2-3 (dài 2) là dãy đầu tiên ≥ 2 → bắt đầu tại 2. In 4 và 2.

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

      Dòng 1: n. Dòng 2: chuỗi n ký tự 0/1. Dòng 3: need — số block liên tiếp cần cấp.

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

      1 ≤ n ≤ 10^5; bitmap dài đúng n; 1 ≤ need ≤ n.

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

      Dòng 1: số block trống. Dòng 2: chỉ số bắt đầu vùng cấp (first-fit) hoặc -1.

    Ví dụ:

    Đầu vào:

    8
11000110
2

    Đầu ra:

    4
2

    Giải thích:

    bitmap 11000110: số bit 0 = 4. Quét tìm dãy 0 liên tiếp ≥2: vị trí 2,3 là dãy đầu tiên đủ dài → bắt đầu 2. In 4 và 2.

    Đang tải editor...