Bộ nhớ gồm các lỗ trống (free holes) có kích thước cho trước, sắp theo địa chỉ tăng dần. Có một dãy yêu cầu cấp phát, dùng chiến lược First-Fit (cấp vào lỗ ĐẦU TIÊN đủ lớn theo thứ tự địa chỉ). Khi cấp phát s vào một lỗ kích thước h ≥ s, lỗ đó còn lại h − s (vẫn ở vị trí cũ). Yêu cầu không vừa lỗ nào thì bỏ qua (không cấp).
Sau khi xử lý hết các yêu cầu, phân mảnh ngoài (external fragmentation) = tổng kích thước tất cả các lỗ còn trống lớn hơn 0.
In ra hai số cách nhau dấu cách: tổng bộ nhớ còn trống (external fragmentation) và số yêu cầu bị từ chối.
Ví dụ: lỗ [10, 5, 8], yêu cầu [6, 4, 9]. 6->lỗ1(còn4). 4->lỗ1(còn0)... mô phỏng first-fit từng bước.
Dòng đầu: H (số lỗ). Dòng tiếp: H kích thước lỗ (theo địa chỉ tăng dần). Dòng tiếp: Q (số yêu cầu). Dòng tiếp: Q kích thước yêu cầu.
1 ≤ H ≤ 100000; 1 ≤ Q ≤ 100000; kích thước ≥ 1.
Hai số: tổng bộ nhớ trống còn lại (phân mảnh ngoài) và số yêu cầu bị từ chối.
Ví dụ:
Đầu vào:
3
10 5 8
3
6 4 9
Đầu ra:
13 1
Giải thích:
Đang tải editor...