Hệ thống đám mây DUT
Đề bài
Mô tả
Tuần trước, chúng ta đã giúp trường HCMUS tính tốc độ truyền dữ liệu giữa máy chủ của họ. Hệ thống đó hoạt động rất tốt và trở thành hình mẫu cho các trường đại học khác. Trường Đại học Bách khoa Đà Nẵng (DUT) muốn xây dựng một hệ thống tương tự.
DUT đã có sẵn máy chủ, họ muốn kết nối chúng bằng các dây cáp hai chiều. Mỗi cặp máy chủ được nối bởi nhiều nhất dây cáp (có thể không có dây nào).
Dây cáp nối máy chủ và máy chủ có khả năng truyền tải 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; tổng lượng dữ liệu đi qua mỗi dây cáp không vượt quá khả năng truyền tải của dây đó. Nói cách khác, là luồng cực đại giữa và trong mạng dây cáp.
Ví dụ, xét mạng máy chủ với các dây cáp (), (), (), (), (). Để truyền dữ liệu từ máy chủ đến máy chủ , dữ liệu có thể chia thành phần và truyền theo đường:
- ( Mb mỗi nano giây);
- ( Mb mỗi nano giây);
- ( Mb mỗi nano giây);
nên tốc độ truyền từ đến là Mb mỗi nano giây, tức . Trong ví dụ này, ma trận tốc độ truyền đầy đủ là:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 60 | 60 | 60 |
| 2 | 60 | 0 | 60 | 60 |
| 3 | 60 | 60 | 0 | 90 |
| 4 | 60 | 60 | 90 | 0 |
DUT có ma trận tốc độ truyền mong muốn . Nhiệm vụ của bạn là giúp họ chọn các dây cáp và cách nối máy chủ để đạt được đúng ma trận tốc độ truyền . Có thể có nhiều cấu hình cùng đạt được điều đó; chẳng hạn với ma trận trên, mạng gồm các dây cáp (), , , , , (mỗi dây ) cũng cho đúng ma trận này.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên : số bộ test. Tiếp theo là bộ test:
- Mỗi bộ test bắt đầu bằng số nguyên ().
- dòng tiếp theo, mỗi dòng chứa số nguyên mô tả ma trận .
- Dữ liệu đảm bảo , , .
- Tổng của mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một dòng Case #t: YES hoặc Case #t: NO ( là số thứ tự bộ test, bắt đầu từ ) tùy theo có thể hay không thể đạt được ma trận tốc độ truyền . Nếu có thể, dòng tiếp theo mô tả cấu hình của bạn: số thứ trên dòng thứ là . Bạn phải đảm bảo , và ( nghĩa là không có dây cáp giữa và ).
Nếu có nhiều cấu hình thỏa mãn, in ra một cấu hình bất kỳ.
Ràng buộc
- , tổng không vượt quá .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 0 1 2 1 0 4 2 4 0 4 0 60 60 60 60 0 60 60 60 60 0 90 60 60 90 0 |
Case #1: NO Case #2: YES 0 60 60 0 60 0 0 0 60 0 0 90 0 0 90 0 |
Ở bộ test thứ nhất, nhưng và : dữ liệu có thể đi từ đến rồi từ đến với tốc độ , nên không thể có . Ở bộ test thứ hai, cấu hình được in gồm các dây (), (), (). Cấu hình trong đề gốc (, , mỗi dây và dây ) cũng đúng. |
| 4 1 0 2 0 0 0 0 2 0 5 5 0 3 0 0 5 0 0 5 5 5 0 |
Case #1: YES 0 Case #2: YES 0 0 0 0 Case #3: YES 0 5 5 0 Case #4: NO |
Ví dụ bổ sung (không có trong đề gốc). Bộ test thứ tư không thể đạt được: nếu máy chủ và đều truyền được tới máy chủ thì chúng truyền được cho nhau qua máy chủ , nên không thể bằng . |
Bình luận