NOI Singapore 2026 - Airplane 2
Xem PDFTrên một máy bay có \(h\) hàng ghế và \(w\) cột ghế. Hàng được đánh số từ \(1\) đến \(h\) theo chiều từ trên xuống, cột được đánh số từ \(1\) đến \(w\) theo chiều từ trái sang. Ghế ở hàng \(i\), cột \(j\) được ký hiệu \((i,j)\).
Pan bán vé cho \(k\) hành khách, đánh số từ \(1\) đến \(k\). Hành khách thứ \(i\) có cột đã định \(c_i\); Pan được chọn một hàng \(r_i\) bất kỳ cho người đó. Không được có hai hành khách ngồi cùng một ghế.
Để bảo đảm cân bằng, hành khách ở hàng trước không được ngồi ở cột nằm sau. Nói cách khác, với hai ghế đã gán \((a_1,b_1)\) và \((a_2,b_2)\), nếu \(a_1<a_2\) thì phải có \(b_1\le b_2\).
Độ hài lòng chung là khoảng cách Manhattan nhỏ nhất giữa mọi cặp ghế đã gán. Khoảng cách giữa \((a_1,b_1)\) và \((a_2,b_2)\) là
Hãy tìm độ hài lòng chung lớn nhất trong mọi cách gán hàng hợp lệ, hoặc xác định rằng không tồn tại cách gán hợp lệ.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên \(h,w,k\).
- Dòng thứ hai chứa \(k\) số nguyên \(c_1,c_2,\ldots,c_k\).
Dữ liệu ra
In độ hài lòng chung lớn nhất. Nếu không có cách gán hợp lệ, in \(-1\).
Giới hạn
Chấm điểm
| Phần | Điểm | Giới hạn thêm |
|---|---|---|
| 1 | 5 | \(w=1\) |
| 2 | 5 | \(c_i=i\) với mọi \(1\le i\le k\) |
| 3 | 7 | \(c\) là cấp số cộng: \(c_{i+1}-c_i=c_i-c_{i-1}\) với mọi \(2\le i<k\) |
| 4 | 9 | \(h,w,k\le8\) |
| 5 | 31 | \(h,w,k\le3000\) |
| 6 | 16 | Các \(c_i\) đôi một khác nhau |
| 7 | 27 | Không có giới hạn thêm |
Ví dụ
Ví dụ 1
Input
5 1 6
1 1 1 1 1 1Output
-1Note
Máy bay chỉ có \(5\) ghế nên không thể xếp \(6\) hành khách vào các ghế khác nhau.
Ví dụ 2
Input
2 7 3
1 2 3Output
1Ví dụ 3
Input
3 7 3
1 4 7Output
4Ví dụ 4
Input
50 50 10
34 21 28 44 41 28 5 10 16 24Output
9Ví dụ 5
Input
4 11 5
1 1 11 7 3Output
2Note
Một cách tối ưu là xếp hành khách thứ nhất ở hàng \(1\) và các hành khách còn lại ở hàng \(4\). Khoảng cách nhỏ nhất là khoảng cách giữa ghế \((4,1)\) và \((4,3)\), bằng \(2\).
Hình 1: Một cách xếp hợp lệ tối ưu cho ví dụ 5.
Hình 2: Một cách xếp không hợp lệ vì vi phạm điều kiện cân bằng giữa thứ tự hàng và cột.
Kỳ thi:
- NOI Singapore 2026 - Vòng sơ khảo (17 Tháng 1., 2026)
Bình luận