Công lý cho loài kiến
Đề bài
Mô tả
Kiến Chimera là một loài kiến thông minh và chăm chỉ.
Có một đàn kiến Chimera sống ở Đà Nẵng, Việt Nam. Nhờ quy hoạch hạ tầng cẩn thận và làm việc chăm chỉ, chúng đã xây dựng vương quốc gồm thị trấn, đánh số từ đến . Các thị trấn được nối với nhau bởi con đường hai chiều sao cho giữa hai thị trấn bất kỳ có đúng một đường đi đơn.
Mùa đông đang đến! Kiến Chúa dự định phân phát thức ăn cho thị trấn: thị trấn thứ sẽ nhận đơn vị thức ăn.
Tuy nhiên, đàn kiến cảm thấy kế hoạch này không công bằng. Chúng đòi công lý! Chúng gửi lên yêu cầu. Mỗi yêu cầu cho bốn thị trấn , , , sao cho khoảng cách từ đến bằng khoảng cách từ đến . Ở đây khoảng cách từ thị trấn đến thị trấn là số con đường trên đường đi đơn duy nhất từ đến .
Gọi là đường đi đơn từ đến , và là đường đi đơn từ đến . Yêu cầu nói rằng với mọi từ đến , thị trấn và thị trấn phải nhận lượng thức ăn bằng nhau.
Việc thay đổi kế hoạch phân phát hóa ra là một bài toán khó. Kiến Chúa có một số nguyên không âm , và mỗi giây bà có thể thay đổi kế hoạch bằng các bước sau:
- Chọn một số nguyên .
- Chọn một thị trấn .
- Tăng hoặc giảm lượng thức ăn của thị trấn đi . Nói cách khác, Kiến Chúa có thể gán hoặc . Sau bước này phải là số nguyên không âm, vì không thể phân phát lượng thức ăn âm.
Hỏi Kiến Chúa cần ít nhất bao nhiêu giây để thay đổi kế hoạch sao cho thỏa mãn mọi yêu cầu?
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và : số thị trấn, số yêu cầu và số nguyên của Kiến Chúa (, , ).
Dòng thứ hai chứa số nguyên (), trong đó là lượng thức ăn ban đầu dự định cho thị trấn .
dòng tiếp theo chứa số nguyên (), mỗi số trên một dòng, nghĩa là có một con đường hai chiều nối thị trấn với thị trấn .
Mỗi dòng trong dòng tiếp theo chứa bốn số nguyên , , , mô tả một yêu cầu (). Dữ liệu đảm bảo hai đường đi đơn từ đến và từ đến có cùng độ dài.
Dữ liệu đảm bảo giữa hai thị trấn bất kỳ có đúng một đường đi đơn, và luôn có thể thỏa mãn cả yêu cầu.
Dữ liệu ra
In ra một số nguyên là số giây ít nhất mà Kiến Chúa cần để thay đổi kế hoạch phân phát thức ăn.
Ràng buộc
- , , .
- .
- .
- , đường đi từ đến và từ đến có cùng độ dài.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 0 3 1 1 2 1 1 1 3 3 2 3 4 5 1 3 3 4 4 4 5 5 |
3 | Có con đường: , , và . Vì nên mỗi giây Kiến Chúa chỉ có thể tăng hoặc giảm một đi . Một cách tối ưu là giảm xuống và giảm xuống , mất giây. |
| 1 1 5 7 1 1 1 1 |
0 | Ví dụ bổ sung (không có trong đề gốc). Chỉ có một thị trấn, yêu cầu luôn được thỏa mãn nên không cần thay đổi gì. |
Bình luận