Hệ thống đám mây
Đề bài
Mô tả
Trường Đại học Khoa học Tự nhiên TP. Hồ Chí Minh vừa xây dựng một hệ thống điện toán đám mây mới để chạy các thí nghiệm cho những nghiên cứu liên quan đến học sâu.
Hệ thống gồm máy chủ (đánh số từ đến ). Mỗi cặp máy chủ được nối với nhau bởi nhiều nhất sợi cáp (có thể không có sợi nào). Sợi cáp nối máy chủ và máy chủ có khả năng truyền megabit mỗi nano giây.
Gọi là tốc độ truyền dữ liệu giữa máy chủ và máy chủ . Để truyền dữ liệu từ máy chủ đến máy chủ , dữ liệu có thể được chia thành nhiều phần và truyền theo nhiều đường khác nhau.
Ví dụ, với mạng gồm các cáp (), (), (), () và (), để truyền dữ liệu từ máy chủ đến máy chủ , có thể chia dữ liệu thành phần và truyền theo đường sau:
- ( megabit mỗi nano giây);
- ( megabit mỗi nano giây);
- ( megabit mỗi nano giây);
nên tốc độ truyền từ đến là megabit mỗi nano giây, tức là .
Cho cấu hình của mạng và khả năng truyền của các sợi cáp, nhiệm vụ của bạn là tính ma trận .
Dữ liệu vào
- Dòng đầu tiên chứa là số bộ dữ liệu. Tiếp theo là bộ dữ liệu.
- Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa là số máy chủ trong mạng ().
- dòng tiếp theo, mỗi dòng chứa số nguyên: số thứ trên dòng thứ là (; nghĩa là không có cáp nối và ).
Dữ liệu đảm bảo và . Tổng của mọi bộ dữ liệu không vượt quá .
Dữ liệu ra
Với bộ dữ liệu thứ , in ra dòng "Case #t:", sau đó in ra dòng là ma trận kích thước (quy ước ).
Ràng buộc
- , tổng không vượt quá .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 0 50 20 30 50 0 0 10 20 0 0 70 30 10 70 0 4 0 10 0 0 10 0 0 0 0 0 0 10 0 0 10 0 |
Case #1: 0 60 60 60 60 0 60 60 60 60 0 90 60 60 90 0 Case #2: 0 10 0 0 10 0 0 0 0 0 0 10 0 0 10 0 |
Bộ thứ nhất là mạng trong ví dụ của đề: ; giữa và có thể truyền trực tiếp và thêm qua máy chủ , nên . Trong bộ thứ hai, và không nối với nhau. |
| 2 1 0 3 0 5 0 5 0 7 0 7 0 |
Case #1: 0 Case #2: 0 5 5 5 0 7 5 7 0 |
Một máy chủ duy nhất; đường bị giới hạn bởi cáp . |
Bình luận