Những con sông dài nhất
Đề bài
Mô tả
Hệ thống sông Chao Phraya là hệ thống sông chính của Thái Lan. Sáu con sông dài nhất của hệ thống, liệt kê theo độ dài giảm dần, là:
- Tha Chin ( km)
- Nan ( km)
- Yom ( km)
- Ping ( km)
- Pa Sak ( km)
- Wang ( km)
Hình dưới là mô hình đơn giản hóa của hệ thống sông này, trong đó các số trên cạnh là độ dài của từng đoạn sông. Điểm mà hai hay nhiều con sông gặp nhau khi chảy xuôi dòng gọi là một hợp lưu. Các hợp lưu được đánh số. Trong mô hình này, mỗi con sông hoặc kết thúc tại một hợp lưu, hoặc chảy ra biển; biển được đánh số là hợp lưu đặc biệt . Khi hai hay nhiều con sông gặp nhau tại một hợp lưu (khác hợp lưu ), con sông hợp thành sau đó mang tên của một trong các con sông đó. Ví dụ, sông Ping và sông Wang gặp nhau tại hợp lưu , con sông hợp thành giữ tên Ping. Với cách đặt tên này, sông Ping dài km còn sông Wang chỉ dài km. Nếu con sông hợp thành được đặt tên là Wang thì sông Wang sẽ dài km còn sông Ping chỉ dài km.
dot
digraph {
rankdir=LR;
node [shape=circle];
PaSak [shape=box, label="Pa Sak"];
Nan [shape=box];
Yom [shape=box];
Wang [shape=box];
Ping [shape=box];
ThaChin [shape=box, label="Tha Chin"];
Wang -> 1 [label="335", color=blue];
Ping -> 1 [label="305", color=red];
1 -> 0 [label="353", color=red];
Yom -> 2 [label="700", color=orange];
Nan -> 2 [label="675", color=purple];
2 -> 0 [label="65", color=purple];
PaSak -> 0 [label="513", color=green];
ThaChin -> 0 [label="765"];
}
Hệ thống sông trong ví dụ thứ nhất. Các cạnh cùng màu thuộc cùng một con sông.
Việc mọi người ngày càng để ý tới hiện tượng này gây ra sự ganh đua gay gắt giữa các thị trấn ven sông. Chẳng hạn, người dân sống dọc sông Wang phản đối rằng biết đâu với một cách đặt tên hợp lý, con sông của họ thực ra có thể là dài nhất, hoặc dài thứ hai (hoặc ít nhất là không đứng cuối!). Để chấm dứt mọi phỏng đoán, nhiệm vụ của bạn là kiểm chứng tất cả những tuyên bố như vậy.
Thứ hạng của một con sông là vị trí của nó trong danh sách tất cả các con sông sắp theo độ dài giảm dần, thứ hạng tốt nhất là dành cho con sông dài nhất. Với mỗi con sông, hãy xác định thứ hạng tốt nhất có thể của nó xét trên mọi cách đặt tên. Tại mỗi hợp lưu, trong mọi cách đặt tên, tên của con sông mới (lớn hơn) phải là một trong các tên của những con sông nhỏ hơn đổ vào hợp lưu đó. Nếu hai hay nhiều con sông có độ dài bằng nhau trong một cách đặt tên, tất cả các con sông bằng nhau đó đều được coi là có thứ hạng tốt nhất có thể. Ví dụ, nếu một con sông dài nhất và mọi con sông còn lại có độ dài bằng nhau thì các con sông còn lại đều có thứ hạng .
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên () là số nguồn sông trong hệ thống và () là số hợp lưu có nhãn dương. Các hợp lưu này được đánh số từ tới .
dòng tiếp theo mô tả các con sông. Mỗi dòng gồm một xâu là tên của con sông tại nguồn, và hai số nguyên () và (), trong đó là số hiệu của hợp lưu gần nhất ở hạ lưu và là khoảng cách (tính bằng km) từ nguồn tới hợp lưu đó. Tên sông chỉ gồm các chữ cái thường và hoa từ a tới z, có độ dài từ tới ký tự.
dòng cuối mô tả các hợp lưu tới theo cách tương tự. Dòng thứ trong số này mô tả hợp lưu có số hiệu và chứa hai số nguyên: số hiệu của hợp lưu gần nhất ở hạ lưu và khoảng cách (tính bằng km) từ hợp lưu tới hợp lưu đó.
Dữ liệu bảo đảm mỗi hợp lưu từ tới xuất hiện ít nhất hai lần với vai trò "hợp lưu gần nhất ở hạ lưu", hợp lưu xuất hiện ít nhất một lần, và mọi nguồn sông đều chảy tới hợp lưu .
Dữ liệu ra
In mỗi con sông trên một dòng, theo đúng thứ tự trong dữ liệu vào. Trên mỗi dòng in tên con sông và thứ hạng tốt nhất có thể của nó.
Ràng buộc
- , .
- , (với cả nguồn sông và hợp lưu).
- Tên sông gồm từ tới chữ cái tiếng Anh thường hoặc hoa.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 PaSak 0 513 Nan 2 675 Yom 2 700 Wang 1 335 Ping 1 305 ThaChin 0 765 0 353 0 65 |
PaSak 5 Nan 2 Yom 1 Wang 3 Ping 4 ThaChin 1 |
Hệ thống sông trong hình. Nếu hợp lưu mang tên Wang thì Wang dài km; khi đó dù đặt tên thế nào, Tha Chin ( km) và một trong hai sông Nan ( km nếu hợp lưu mang tên Nan) hoặc Yom ( km nếu mang tên Yom) vẫn dài hơn, nên thứ hạng tốt nhất của Wang là . |
| 3 1 Ab 1 5 Cd 1 5 Ef 0 9 0 4 |
Ab 1 Cd 1 Ef 1 |
Ab và Cd gặp nhau tại hợp lưu . Con sông được chọn đi tiếp dài km, bằng sông Ef, con còn lại dài km. Mỗi sông đều có thể đạt thứ hạng vì các sông dài bằng nhau cùng nhận thứ hạng tốt nhất. |
Bình luận