3. IOI 2015 - Towns
Kazakhstan có \(N\) thị trấn nhỏ, đánh số từ \(0\) đến \(N-1\), và một số lượng chưa biết các thành phố lớn. Các thị trấn nhỏ và thành phố lớn được gọi chung là các đô thị.
Tất cả đô thị được nối bởi một mạng đường cao tốc hai chiều duy nhất. Mỗi đường nối hai đô thị khác nhau; giữa một cặp đô thị có nhiều nhất một đường nối trực tiếp. Với mỗi cặp đô thị \(a\), \(b\), có duy nhất một cách đi từ \(a\) đến \(b\) bằng các đường cao tốc mà không sử dụng đường nào quá một lần.
Mỗi thị trấn nhỏ nối trực tiếp với đúng một đô thị khác; mỗi thành phố lớn nối trực tiếp với ít nhất ba đô thị.
Hình sau minh họa mạng gồm \(11\) thị trấn nhỏ và \(7\) thành phố lớn. Thị trấn được vẽ bằng hình tròn, ghi nhãn số nguyên; thành phố được vẽ bằng hình vuông, ghi nhãn chữ cái.
Mỗi đường cao tốc có độ dài nguyên dương. Khoảng cách giữa hai đô thị là tổng độ dài nhỏ nhất của các đường cần đi qua để từ đô thị này tới đô thị kia.
Với thành phố lớn \(C\), gọi \(r(C)\) là khoảng cách từ \(C\) đến thị trấn nhỏ xa nó nhất. Thành phố lớn \(C\) là một hub nếu \(r(C)\) nhỏ nhất trong số tất cả các thành phố lớn. Ký hiệu \(R\) là khoảng cách từ một hub đến thị trấn nhỏ xa nó nhất; như vậy \(R\) là giá trị nhỏ nhất trong tất cả các \(r(C)\).
Trong hình, thị trấn xa thành phố \(a\) nhất là thị trấn \(8\), với
Thành phố \(g\) cũng có \(r(g)=17\); một thị trấn xa \(g\) nhất là thị trấn \(6\). Hub duy nhất là thành phố \(f\), với \(r(f)=16\), nên \(R=16\).
Loại bỏ một hub sẽ chia mạng thành nhiều thành phần liên thông. Hub là cân bằng nếu mỗi thành phần chứa không quá \(\lfloor N/2\rfloor\) thị trấn nhỏ. Chỉ đếm thị trấn nhỏ, không đếm thành phố lớn. Ký hiệu \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).
Trong ví dụ, loại bỏ \(f\) tạo thành bốn thành phần có các tập thị trấn \(\{0,1,10\}\), \(\{2,3\}\), \(\{4,5,6,7\}\) và \(\{8,9\}\). Không thành phần nào có quá \(\lfloor 11/2\rfloor=5\) thị trấn nhỏ, nên \(f\) là hub cân bằng.
Chi tiết cài đặt
Ban đầu bạn chỉ biết \(N\), số thị trấn nhỏ; không biết số thành phố lớn hay cách bố trí đường cao tốc. Bạn chỉ có thể lấy thêm thông tin bằng cách hỏi khoảng cách giữa hai thị trấn nhỏ.
Cần xác định \(R\) trong mọi subtask. Với subtasks \(3\) đến \(6\), còn phải xác định có tồn tại hub cân bằng hay không.
Trong C hoặc C++, cài đặt hàm sau trong header dùng chung towns.h:
int hubDistance(int N, int sub);
Chương trình chấm cung cấp hàm:
int getDistance(int i, int j);
Trong Java, cài đặt phương thức trong lớp towns:
public int hubDistance(int N, int sub)
Gọi phương thức do chương trình chấm cung cấp qua grader.lib.getDistance(i, j):
public static int getDistance(int i, int j)
Trong một lần chạy, chương trình chấm xét nhiều test, tối đa \(40\) test. Với mỗi test, hubDistance được gọi đúng một lần. Phải khởi tạo lại mọi biến cần thiết ở mỗi lần gọi.
N: số thị trấn nhỏ.sub: số hiệu subtask, như bảng bên dưới.- Nếu
subbằng \(1\) hoặc \(2\), có thể trả về \(R\) hoặc \(-R\). - Nếu
sublớn hơn \(2\), phải trả về \(R\) khi có hub cân bằng, và \(-R\) khi không có. getDistance(i, j)trả về khoảng cách giữa hai thị trấn nhỏ \(i\) và \(j\). Nếu \(i=j\) thì trả về \(0\); nếu đối số không hợp lệ cũng trả về \(0\). Mỗi lần gọi vẫn được tính vào giới hạn truy vấn.
Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "towns.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp towns, không viết phương thức main. Không đọc trực tiếp ma trận khoảng cách bí mật; chỉ dùng getDistance để lấy thông tin.
Phân nhóm
Trong mỗi test:
- \(6 \le N \le 110\).
- Khoảng cách giữa hai thị trấn nhỏ khác nhau thuộc đoạn \([1,1000000]\).
Số lần gọi getDistance bị giới hạn theo subtask. Nếu vượt giới hạn, chương trình bị dừng và test được xem là trả lời sai. Mỗi subtask được trọn điểm nếu tất cả test của subtask đều đúng, nếu không được \(0\) điểm. Test mẫu là pretest \(0\) điểm.
| Subtask | Điểm | Số truy vấn tối đa | Phải xác định hub cân bằng | Ràng buộc bổ sung |
|---|---|---|---|---|
| 1 | 13 | \(N(N-1)/2\) | Không | Không có. |
| 2 | 12 | \(\lceil 7N/2\rceil\) | Không | Không có. |
| 3 | 13 | \(N(N-1)/2\) | Có | Không có. |
| 4 | 10 | \(\lceil 7N/2\rceil\) | Có | Mỗi thành phố lớn nối trực tiếp với đúng ba đô thị. |
| 5 | 13 | \(5N\) | Có | Không có. |
| 6 | 39 | \(\lceil 7N/2\rceil\) | Có | Không có. |
Ký hiệu \(\lceil x\rceil\) là số nguyên nhỏ nhất lớn hơn hoặc bằng \(x\).
Chương trình chấm mẫu
Số hiệu subtask là một phần của dữ liệu vào; chương trình chấm mẫu thay đổi hành vi theo số hiệu đó. Chương trình đọc tệp towns.in theo định dạng:
- Dòng \(1\): số hiệu subtask và số test.
- Dòng \(2\): \(N_1\), số thị trấn nhỏ của test đầu tiên.
- \(N_1\) dòng tiếp theo: số thứ \(j\) (\(1 \le j \le N_1\)) trên dòng thứ \(i\) (\(1 \le i \le N_1\)) là khoảng cách giữa thị trấn \(i-1\) và \(j-1\).
- Các test tiếp theo có cùng định dạng như test đầu tiên.
Đề chính thức mô tả chương trình chấm mẫu in giá trị trả về của hubDistance và số truy vấn trên hai dòng riêng biệt. Mã grader thực tế trong gói chính thức chỉ in giá trị trả về; grader LQDOJ giữ cách in này, kiểm soát số truy vấn bên trong và chuyển phần đọc/ghi sang đầu vào/đầu ra chuẩn.
Dữ liệu tương ứng với hình trên:
1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0Một kết quả hợp lệ của grader trong gói đính kèm và trên LQDOJ:
16Định dạng ma trận này khác với việc liệt kê các đường cao tốc. Bạn được phép sửa chương trình chấm mẫu để dùng định dạng đầu vào khác khi thử chương trình của mình.