JOI 2024 - Heat Stroke
Xem PDFĐảo JOI gồm \(L\) khu vực, đánh số từ \(1\) đến \(L\) theo thứ tự từ tây sang đông. Trên đảo có \(L-1\) con đường, đánh số từ \(1\) đến \(L-1\). Đường \(i\) (\(1\le i\le L-1\)) nối hai khu vực \(i\) và \(i+1\) theo cả hai chiều.
Trong hình, các ô lần lượt biểu diễn khu vực \(1,2,3,\ldots,L\); đường \(1\) nối khu vực \(1\) với khu vực \(2\), đường \(2\) nối khu vực \(2\) với khu vực \(3\).
Olympic Tin học Quốc tế IOI 20XX dự kiến được tổ chức trên đảo JOI. Tuy nhiên, hòn đảo nổi tiếng với thời tiết cực kỳ nóng. Nguy cơ sốc nhiệt rất cao, đặc biệt với các thí sinh nước ngoài chưa quen khí hậu nóng. Vì vậy, ban tổ chức quyết định thực hiện các biện pháp sau:
- Với mỗi khu vực \(i\) (\(1\le i\le L\)), chuẩn bị một bệnh viện có sức chứa \(C_i\) người. Có thể có \(C_i=0\).
- Khi một người trên đường \(x\) (\(1\le x\le L-1\)) bị sốc nhiệt, đưa người đó tới bệnh viện ở khu vực \(x\) hoặc \(x+1\) còn chỗ. Nếu cả hai bệnh viện đều còn chỗ, có thể chọn bất kỳ bệnh viện nào trong hai bệnh viện đó. Nếu cả hai đều đã đầy, đưa bệnh nhân bằng trực thăng tới một bệnh viện đa khoa ở ngoài đảo.
Việc sử dụng trực thăng rất tốn kém, nên ban tổ chức muốn ước lượng số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng. Họ xét kịch bản sau:
- Trước khi IOI diễn ra, tất cả bệnh viện đều không có bệnh nhân.
- Trong thời gian tổ chức IOI, có \(N\) người bị sốc nhiệt trên đảo. Bệnh nhân thứ \(j\) (\(1\le j\le N\)) xuất hiện trên đường \(X_j\).
- Với mỗi \(1\le j\le N-1\), khi bệnh nhân thứ \(j+1\) bị sốc nhiệt thì bệnh nhân thứ \(j\) và mọi bệnh nhân trước đó đã được đưa tới bệnh viện. Do triệu chứng sốc nhiệt nghiêm trọng, không bệnh nhân nào rời bệnh viện trong suốt thời gian tổ chức IOI.
Cho số khu vực, thông tin bệnh viện và các bệnh nhân, hãy tính số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng trong kịch bản trên.
Dữ liệu vào
Đọc từ đầu vào chuẩn theo định dạng:
L
C_1 C_2 ... C_L
N
X_1 X_2 ... X_N
Dữ liệu ra
Xuất một dòng chứa số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng.
Ràng buộc
- \(2\le L\le 8\,000\).
- \(0\le C_i\le 8\,000\) với \(1\le i\le L\).
- \(1\le N\le 8\,000\).
- \(1\le X_j\le L-1\) với \(1\le j\le N\).
- Tất cả giá trị đầu vào đều là số nguyên.
Phân nhóm
Mọi nhóm đều tuân theo các ràng buộc chung ở trên.
| Nhóm | Điểm | Ràng buộc bổ sung |
|---|---|---|
| 1 | 6 | \(X_1\le X_2\le\cdots\le X_N\). |
| 2 | 7 | \(L\le 18\), \(N\le 18\) và \(C_i=1\) với mọi \(1\le i\le L\). |
| 3 | 7 | \(L\le 18\), \(N\le 100\) và \(C_i=1\) với mọi \(1\le i\le L\). |
| 4 | 25 | \(L\le 100\), \(N\le 100\) và \(C_i=1\) với mọi \(1\le i\le L\). |
| 5 | 25 | \(L\le 100\), \(N\le 100\). |
| 6 | 10 | \(L\le 600\), \(N\le 600\). |
| 7 | 15 | \(L\le 3\,500\), \(N\le 3\,500\). |
| 8 | 5 | Không có ràng buộc bổ sung. |
Ví dụ
Ví dụ 1
Input
3
1 1 1
3
1 2 2Output
1Note
Có thể phải vận chuyển \(1\) bệnh nhân bằng trực thăng nếu xử lý như sau:
- Đưa bệnh nhân thứ \(1\) tới bệnh viện ở khu vực \(2\). Số bệnh nhân tại các khu vực \(1,2,3\) lần lượt là \(0,1,0\).
- Đưa bệnh nhân thứ \(2\) tới bệnh viện ở khu vực \(3\). Số bệnh nhân tại các khu vực \(1,2,3\) lần lượt là \(0,1,1\).
- Với bệnh nhân thứ \(3\), cả hai bệnh viện ở khu vực \(2,3\) đều đã đầy, nên phải đưa người đó bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
Không có cách nào khiến từ \(2\) bệnh nhân trở lên phải đi bằng trực thăng, nên kết quả là \(1\). Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm \(1,2,3,4,5,6,7,8\).
Ví dụ 2
Input
6
1 1 1 1 1 1
7
1 3 5 4 2 2 3Output
3Note
Có thể phải vận chuyển \(3\) bệnh nhân bằng trực thăng nếu xử lý như sau:
- Đưa bệnh nhân thứ \(1\) tới bệnh viện ở khu vực \(2\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,0,0,0\).
- Đưa bệnh nhân thứ \(2\) tới bệnh viện ở khu vực \(4\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,1,0,0\).
- Đưa bệnh nhân thứ \(3\) tới bệnh viện ở khu vực \(5\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,1,1,0\).
- Với bệnh nhân thứ \(4\), cả hai bệnh viện ở khu vực \(4,5\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
- Đưa bệnh nhân thứ \(5\) tới bệnh viện ở khu vực \(3\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,1,1,1,0\).
- Với bệnh nhân thứ \(6\), cả hai bệnh viện ở khu vực \(2,3\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
- Với bệnh nhân thứ \(7\), cả hai bệnh viện ở khu vực \(3,4\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
Không có cách nào khiến từ \(4\) bệnh nhân trở lên phải đi bằng trực thăng, nên kết quả là \(3\). Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4,5,6,7,8\).
Ví dụ 3
Input
6
4000 1 1 0 4000 1
5
1 1 2 3 5Output
1Note
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,5,6,7,8\).
Ví dụ 4
Input
5
1 2 2 2 1
8
2 3 2 1 4 1 2 3Output
2Note
Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).
Ví dụ 5
Input
10
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8Output
3Note
Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).
Nguồn
JOI Open Contest 2024, bài Heat Stroke, tác giả Hirotaka Yoneda và Masataka Yoneda.
Bản dịch tiếng Việt và hình từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2024 - Open Contest (16 Tháng sáu, 2024)
Bình luận