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] Inode — định vị block trực tiếp/gián tiếp

    Một inode kiểu Unix có:

    • D con trỏ trực tiếp (direct), mỗi con trỏ trỏ tới 1 block dữ liệu.
    • 1 con trỏ gián tiếp đơn (single indirect): trỏ tới 1 block chỉ mục, block đó chứa K con trỏ tới block dữ liệu (K = số con trỏ vừa trong một block).
    • 1 con trỏ gián tiếp đôi (double indirect): trỏ tới 1 block chỉ mục cấp 1, block đó chứa K con trỏ tới các block chỉ mục cấp 2, mỗi block cấp 2 chứa K con trỏ tới block dữ liệu.

    Cho chỉ số block logic b (đánh số từ 0) của một file, hãy xác định block đó được truy cập qua loại con trỏ nào:

    • Nếu b < D: in DIRECT.
    • Nếu D ≤ b < D + K: in SINGLE.
    • Nếu D + K ≤ b < D + K + K·K: in DOUBLE.
    • Ngoài phạm vi trên: in OUT_OF_RANGE.

    Cho Q truy vấn, mỗi truy vấn một giá trị b. In Q dòng kết quả.

    Ví dụ: D=12, K=256. b=5 -> DIRECT. b=12 -> SINGLE (12 ≤ b < 268). b=300 -> DOUBLE. b=99999 -> nếu vượt 12+256+65536=65804 thì OUT_OF_RANGE.

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

      Dòng đầu: D K (số con trỏ trực tiếp, số con trỏ trong một block chỉ mục). Dòng tiếp: Q (số truy vấn). Tiếp theo Q số là các chỉ số block logic b.

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

      1 ≤ D ≤ 100; 1 ≤ K ≤ 100000; 1 ≤ Q ≤ 100000; 0 ≤ b ≤ 10^18.

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

      Q dòng, mỗi dòng một trong: DIRECT, SINGLE, DOUBLE, OUT_OF_RANGE.

    Ví dụ:

    Đầu vào:

    12 256 4
5 12 300 99999

    Đầu ra:

    DIRECT
SINGLE
DOUBLE
OUT_OF_RANGE

    Giải thích:

    D=12, K=256. b=5<12 -> DIRECT. b=12 nằm [12,268) -> SINGLE. b=300 nằm [268, 268+65536) -> DOUBLE. b=99999 > 12+256+65536=65804 -> OUT_OF_RANGE.

    Đang tải editor...