solution

Một quản trị viên cần cấp phát các dải mạng con (subnet) cho $n$ phòng ban từ một dải mạng lớn ban đầu, theo đúng thứ tự yêu cầu được liệt kê (không được sắp xếp lại). Đây là bài toán mô phỏng đơn giản hoá kỹ thuật VLSM, dùng cách cấp phát tuần tự kiểu bump allocator (khác với quy ước căn chỉnh nhị phân trong VLSM chuẩn) để đảm bảo kết quả xác định duy nhất.

Cho dải mạng lớn ban đầu dạng CIDR A.B.C.D/P. Gọi địa chỉ mạng của dải này là điểm bắt đầu, và điểm kết thúc là địa chỉ cuối cùng còn nằm trong dải (địa chỉ mạng $+ 2^{32-P} - 1$).

Với mỗi phòng ban, cho số lượng host tối đa cần dùng $need$ ($1 \le need \le 100000$). Cần tìm độ dài tiền tố $p$ lớn nhất (tức khối địa chỉ nhỏ nhất) sao cho số host sử dụng được $2^{32-p} - 2 \ge need$ (với $0 \le p \le 30$).

Việc cấp phát dùng một con trỏ current (ban đầu bằng địa chỉ mạng của dải lớn):

1. Tính $p$ như trên, khối có kích thước $2^{32-p}$ địa chỉ.
2. Dải con được cấp = từ current đến current + 2^{32-p} - 1.
3. Nếu địa chỉ cuối của dải con này vượt quá điểm kết thúc của dải lớn: phòng ban đó không được cấp phát, in ra OVERFLOW, và current giữ nguyên (không cộng dồn) cho lượt tiếp theo.
4. Nếu không vượt quá: in ra <network>/<p> <broadcast> của dải con vừa cấp, sau đó cập nhật current = broadcast + 1 cho lượt tiếp theo.

Ví dụ:

Input:

192.168.1.0/24
4
100
50
10
200

Output:

192.168.1.0/25 192.168.1.127
192.168.1.128/26 192.168.1.191
192.168.1.192/28 192.168.1.207
OVERFLOW

(Yêu cầu 100 host $\Rightarrow p=25$ (126 host khả dụng); 50 host $\Rightarrow p=26$ (62 host); 10 host $\Rightarrow p=28$ (14 host); yêu cầu cuối 200 host cần khối $p=24$ nhưng đã vượt quá dải /24 ban đầu nên OVERFLOW.)