Thứ hạng thấp nhất
Đề bài
Mô tả
Năm 2050. Sau nhiều lần trì hoãn vì những hoàn cảnh bất thường, Cuộc thi Sửa ống nước Hợp tác Liên lục địa (Intercontinental Cooperative Plumbing Competition, ICPC) cuối cùng cũng được tổ chức! Tham gia cuộc thi có đội thợ sửa ống nước, đã vượt qua các vòng thi khu vực từ năm 2021 cho đến tận năm 2049. Theo truyền thống, ICPC gồm bài toán sửa ống nước, các đội thi đấu để giải được càng nhiều bài càng tốt. Tuy nhiên, khác với những cuộc thi khác có cùng tên viết tắt, chỉ đội đầu tiên giải được một bài mới nhận được một điểm cho bài đó. Sau khi mọi bài đã được giải, các đội được xếp hạng từ đến theo số điểm, các đội có cùng số điểm nhận cùng thứ hạng. Cụ thể, với mỗi đội , thứ hạng của đội bằng số đội có số điểm lớn hơn hẳn số điểm của đội , cộng thêm . Ví dụ, nếu có đội thi bài và các đội giải được đầu tiên lần lượt là và , thì bảng xếp hạng như sau:
- Hạng : đội ( điểm).
- Hạng : các đội , và ( điểm).
- Hạng : đội ( điểm).
Ban tổ chức đã chuẩn bị bài toán. Vì mỗi đội có những điểm mạnh và điểm yếu rất riêng, ban tổ chức biết chắc chắn rằng đội sẽ là đội đầu tiên giải được bài . Không may là, do hoàn cảnh bất thường (lại nữa!), cuộc thi phải rút ngắn. Ban tổ chức quyết định chọn không quá bài liên tiếp cho cuộc thi. Nói cách khác, họ chọn hai chỉ số , sao cho và , rồi chọn các bài cho cuộc thi.
Là một thành viên ban tổ chức và từng là thợ sửa ống nước, MofK rất háo hức muốn biết mỗi đội có thể nhận được những thứ hạng nào. Đội nào cũng có thể vô địch, nhưng tìm thứ hạng thấp nhất (bi quan nhất) có thể của mỗi đội lại không hề đơn giản. Hãy giúp anh ấy trả lời câu hỏi đầy thử thách này!
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, ): số đội thi, số bài đã chuẩn bị và giới hạn số bài của cuộc thi.
- Dòng thứ hai chứa số nguyên (): đội đầu tiên giải được mỗi bài.
Dữ liệu ra
In ra số nguyên trên một dòng, cách nhau bởi dấu cách, trong đó là thứ hạng thấp nhất có thể của đội trong mọi cách chọn bài.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 5 5 1 1 2 3 4 |
4 3 3 4 | Vì , có thể chọn mọi đoạn bài liên tiếp. Đội đứng cuối nếu chọn các bài . Đội đứng thứ ba nếu chọn các bài , và không có cách nào để đội đứng cuối. Đội đứng thứ ba nếu chọn các bài , và không có cách nào để đội đứng cuối. Đội đứng cuối nếu chọn các bài . |
| 5 5 5 1 1 3 2 2 |
3 3 3 4 4 | Đội đứng thứ ba nếu chọn cả bài (các đội và được điểm, đội được điểm); mọi đoạn không chứa bài chỉ có một đội ghi điểm. Các đội và không giải được bài nào; nếu chọn cả bài thì có đội xếp trên họ. |
Bình luận