Nhà vô địch áp đảo
Đề bài
Mô tả
Giải Ngoại hạng Anh (Premier League) có câu lạc bộ. Một trận thắng được điểm, một trận hòa được điểm và một trận thua được điểm. Bảng xếp hạng của giải liệt kê điểm số hiện tại của từng câu lạc bộ (ngoài ra còn có phong độ các trận gần đây, nhưng thông tin này không dùng đến trong bài).
Trong bài toán này, bảng xếp hạng được lấy ngay sau vòng đấu thứ . Do đó, mỗi câu lạc bộ còn đúng trận đấu nữa trước khi mùa giải kết thúc.
Câu lạc bộ có điểm số hiện tại cao nhất được gọi là đội dẫn đầu. Dữ liệu vào đảm bảo có đúng một đội dẫn đầu.
Đội dẫn đầu được gọi là nhà vô địch áp đảo nếu, bất kể điều gì xảy ra trong ba trận đấu còn lại, đội này chắc chắn kết thúc mùa giải với số điểm lớn hơn hẳn (lớn hơn nghiêm ngặt) mọi câu lạc bộ khác.
Bài toán chỉ xét điểm số. Hiệu số bàn thắng bại và mọi quy tắc phân định thứ hạng khác đều bị bỏ qua. Bằng điểm ở vị trí đầu bảng không được coi là vô địch áp đảo.
Trong bài toán này, mỗi câu lạc bộ khác có thể giành thêm nhiều nhất điểm từ ba trận đấu còn lại. Lịch thi đấu chi tiết của các trận còn lại không được cho và không cần xét đến.
Yêu cầu: Hãy xác định xem đội dẫn đầu hiện tại đã chắc chắn trở thành nhà vô địch áp đảo hay chưa.
Dữ liệu vào
Dữ liệu vào gồm đúng dòng. Mỗi dòng chứa tên một câu lạc bộ và số điểm hiện tại của câu lạc bộ đó sau vòng , cách nhau bởi một dấu cách.
Tên câu lạc bộ được viết thành một từ duy nhất: các dấu cách trong tên được thay bằng dấu gạch dưới.
tên câu lạc bộ là: Arsenal, ManCity, ManUtd, AstonVilla, Liverpool, Bournemouth, Sunderland, Brighton, Brentford, Chelsea, Fulham, Newcastle, Everton, Leeds, Palace, NottmForest, Spurs, West_Ham, Burnley và Wolves.
Với mọi câu lạc bộ, .
Mỗi tên trong tên câu lạc bộ xuất hiện đúng một lần (các dòng có thể theo thứ tự bất kỳ).
Có đúng một câu lạc bộ có số điểm hiện tại lớn nhất.
Dữ liệu ra
In ra YES nếu đội dẫn đầu hiện tại chắc chắn là nhà vô địch áp đảo. Ngược lại, in ra NO.
Ràng buộc
- Đúng dòng, mỗi tên câu lạc bộ trong danh sách trên xuất hiện đúng một lần.
- với mọi câu lạc bộ.
- Có đúng một câu lạc bộ có số điểm lớn nhất.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| Arsenal 82 Man_City 69 Man_Utd 66 Aston_Villa 61 Liverpool 60 Bournemouth 55 Sunderland 52 Brighton 50 Brentford 49 Chelsea 48 Fulham 47 Newcastle 46 Everton 44 Leeds 43 Palace 41 Nottm_Forest 40 Spurs 39 West_Ham 35 Burnley 21 Wolves 19 |
YES | Arsenal có điểm. Mỗi câu lạc bộ khác giành thêm được nhiều nhất điểm. Man_City, đối thủ gần nhất, đạt tối đa điểm. Vì vậy Arsenal chắc chắn kết thúc mùa giải với số điểm lớn hơn hẳn. |
| Arsenal 74 Man_City 67 Man_Utd 63 Aston_Villa 59 Liverpool 57 Bournemouth 53 Sunderland 51 Brighton 49 Brentford 48 Chelsea 47 Fulham 45 Newcastle 44 Everton 42 Leeds 41 Palace 40 Nottm_Forest 38 Spurs 37 West_Ham 34 Burnley 20 Wolves 18 |
NO | Man_City vẫn có thể đạt điểm, lớn hơn điểm hiện tại của Arsenal. Vì vậy đội dẫn đầu chưa chắc chắn là nhà vô địch áp đảo. |
Bình luận