JOI Open Contest 2013

Vương quốc JOI sắp tổ chức một cuộc bầu cử toàn quốc. Vương quốc gồm \(N\) tỉnh và được biểu diễn bằng một lưới hình chữ nhật có \(H\) hàng, \(W\) cột. Hai ô được coi là kề nhau nếu chúng có chung một cạnh ở bên trái, bên phải, phía trên hoặc phía dưới. Hai ô chỉ có chung một đỉnh không được coi là kề nhau.

\(H \times W\) ô được chia thành \(N\) tỉnh. Các ô của mỗi tỉnh tạo thành một vùng liên thông: có thể đi từ một ô bất kỳ đến mọi ô khác của tỉnh bằng cách đi qua các ô kề nhau cùng thuộc tỉnh đó. Tỉnh thứ \(i\) có \(P_i\) cử tri.

Bạn là chủ tịch ủy ban bầu cử của vương quốc JOI. Để bầu ra \(K\) đại biểu, bạn phải chia \(N\) tỉnh thành đúng \(K\) khu vực bầu cử, đánh số từ \(1\) đến \(K\). Mỗi tỉnh phải thuộc trọn vẹn một khu vực bầu cử. Mỗi khu vực phải chứa ít nhất một tỉnh, và tất cả các ô thuộc khu vực đó phải tạo thành một vùng liên thông theo cạnh.

Trọng số của một lá phiếu tại một khu vực bầu cử là nghịch đảo của tổng số cử tri trong khu vực đó. Độ chênh lệch giá trị lá phiếu là trọng số lớn nhất chia cho trọng số nhỏ nhất trong tất cả các khu vực bầu cử. Gần đây, độ chênh lệch này đã trở thành một vấn đề xã hội nghiêm trọng, vì vậy bạn muốn làm cho nó nhỏ nhất có thể.

Yêu cầu

Đây là bài chỉ nộp kết quả. Với mỗi bộ dữ liệu được cung cấp, hãy nộp một tệp mô tả cách chia các tỉnh thành các khu vực bầu cử sao cho độ chênh lệch giá trị lá phiếu nhỏ nhất có thể.

Dữ liệu vào

Có năm tệp dữ liệu: 01.txt, 02.txt, 03.txt, 04.txt và 05.txt. Mỗi tệp mô tả một bộ dữ liệu độc lập theo định dạng sau:

• Dòng đầu chứa bốn số nguyên \(H, W, N, K\) cách nhau bởi dấu cách, lần lượt là số hàng, số cột của bản đồ, số tỉnh và số đại biểu cần bầu.
• \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\) trên dòng thứ \(i\) là \(S_{i,j}\), cho biết ô ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang thuộc tỉnh \(S_{i,j}\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(P_i\), là số cử tri của tỉnh thứ \(i\).

Tất cả các bộ dữ liệu thỏa mãn:

• \(1 \le H \le 200\).
• \(1 \le W \le 200\).
• \(1 \le N \le 10\,000\).
• \(1 \le K \le N\).
• \(1 \le S_{i,j} \le N\) với \(1 \le i \le H\), \(1 \le j \le W\).
• \(1 \le P_i \le 100\,000\) với \(1 \le i \le N\).
• Các ô thuộc mỗi tỉnh tạo thành một vùng liên thông.

Dữ liệu ra

Với mỗi tệp dữ liệu 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, nộp một tệp kết quả tương ứng gồm đúng \(N\) dòng. Dòng thứ \(i\) chứa một số nguyên \(E_i\), là số hiệu khu vực bầu cử mà tỉnh thứ \(i\) thuộc về.

Một kết quả hợp lệ phải thỏa mãn \(1 \le E_i \le K\) với mọi \(i\), mỗi số hiệu từ \(1\) đến \(K\) phải xuất hiện ít nhất một lần, và các ô thuộc những tỉnh có cùng số hiệu khu vực bầu cử phải tạo thành một vùng liên thông theo cạnh.

Chấm điểm

Điểm được tính riêng cho từng bộ dữ liệu. Nếu tệp kết quả không thỏa mãn các điều kiện của bài toán, điểm của bộ dữ liệu đó bằng \(0\).

Với một kết quả hợp lệ, gọi \(D\) là độ chênh lệch giá trị lá phiếu của cách phân chia đã nộp. Điểm của bộ dữ liệu là:

Ký hiệu \(\lfloor x \rfloor\) là phần nguyên thu được khi bỏ phần thập phân của giá trị không âm \(x\). Các ngưỡng \(X, Y\) của từng bộ dữ liệu như sau:

Minh họa

Xét bộ dữ liệu sau:

2 3 4 3
1 1 1
2 3 4
3
5
7
10

Bản đồ có hai hàng và ba cột. Cả ba ô ở hàng trên thuộc tỉnh \(1\); ba ô ở hàng dưới lần lượt thuộc các tỉnh \(2, 3, 4\) từ trái sang phải. Số cử tri của bốn tỉnh lần lượt là \(3, 5, 7, 10\).

Một tệp kết quả hợp lệ cho bộ dữ liệu này là:

1
2
1
3

Cách phân chia này gồm:

• Khu vực bầu cử \(1\): tỉnh \(1\) và tỉnh \(3\).
• Khu vực bầu cử \(2\): tỉnh \(2\).
• Khu vực bầu cử \(3\): tỉnh \(4\).

Số cử tri của ba khu vực lần lượt là \(10, 5, 10\), nên trọng số của một lá phiếu lần lượt là \(0.1, 0.2, 0.1\). Do đó, độ chênh lệch giá trị lá phiếu là \(D = 0.2/0.1 = 2\). Nếu các ngưỡng của bộ dữ liệu này là \(X = 1.5\) và \(Y = 3\) thì:

Vì vậy, tệp kết quả này được \(8\) điểm.

Cách phân chia dưới đây không hợp lệ:

• Khu vực bầu cử \(1\): tỉnh \(1\).
• Khu vực bầu cử \(2\): tỉnh \(2\) và tỉnh \(4\).
• Khu vực bầu cử \(3\): tỉnh \(3\).

Lý do là các ô của khu vực bầu cử \(2\) không tạo thành một vùng liên thông.

Công ty JOI có tổng cộng \(N\) máy chủ trên khắp thế giới. Ban đầu, mỗi máy chủ chứa một mẩu thông tin quan trọng, và các mẩu thông tin ban đầu của các máy chủ đôi một khác nhau. Công ty đang xây dựng các đường truyền số giữa các máy chủ để chia sẻ thông tin. Khi có một đường truyền nối hai máy chủ, chúng có thể trao đổi thông tin với nhau. Thông tin cũng có thể được trao đổi giữa hai máy chủ nếu có thể đi từ máy chủ này đến máy chủ kia qua các đường truyền đang hoạt động.

Mỗi máy chủ có một hệ thống đồng bộ hóa hiệu năng cao. Khi hai máy chủ có thể trao đổi thông tin và tập thông tin của chúng khác nhau, chúng tự động đồng bộ hóa. Sau khi máy chủ \(A\) và máy chủ \(B\) đồng bộ hóa, cả hai đều chứa tất cả các mẩu thông tin đã có ở ít nhất một trong hai máy chủ trước khi đồng bộ hóa.

Để giảm chi phí, chỉ có \(N-1\) đường truyền được dự kiến xây dựng. Nếu cả \(N-1\) đường truyền đều hoạt động, giữa hai máy chủ bất kỳ sẽ có đúng một đường đi không đi qua cùng một máy chủ quá một lần.

Ban đầu, tại thời điểm \(0\), chưa có đường truyền nào được xây dựng. Một số đường truyền được xây dựng trong điều kiện khắc nghiệt, chẳng hạn trong sa mạc hoặc dưới đáy biển, nên có thể ngừng hoạt động. Khi một đường truyền ngừng hoạt động, nó không thể được sử dụng cho đến khi được xây dựng lại.

Tại mỗi thời điểm \(j\) với \(1 \le j \le M\), trạng thái của đúng một đường truyền thay đổi. Nếu đường truyền đó không hoạt động ngay trước thời điểm \(j\), nó được xây dựng tại thời điểm \(j\); nếu đang hoạt động, nó ngừng hoạt động tại thời điểm \(j\). Mọi quá trình đồng bộ hóa sau lần thay đổi này đều hoàn tất trước thời điểm \(j+1\). Thông tin đã nhận được vẫn được máy chủ lưu giữ khi đường truyền ngừng hoạt động.

Yêu cầu

Cho các đường truyền dự kiến xây dựng và danh sách các lần thay đổi trạng thái, hãy xác định số mẩu thông tin khác nhau được lưu tại từng máy chủ trong số \(Q\) máy chủ được hỏi ở thời điểm \(M+1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, Q\) cách nhau bởi dấu cách: số máy chủ, số lần thay đổi trạng thái đường truyền và số máy chủ được hỏi.
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i, Y_i\) cách nhau bởi dấu cách. Đường truyền thứ \(i\), khi hoạt động, nối máy chủ \(X_i\) với máy chủ \(Y_i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(D_j\), cho biết đường truyền \(D_j\) thay đổi trạng thái tại thời điểm \(j\).
• \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa số nguyên \(C_k\), là máy chủ cần xác định số mẩu thông tin khác nhau vào cuối quá trình.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(k\) chứa một số nguyên là số mẩu thông tin khác nhau được lưu tại máy chủ \(C_k\) ở thời điểm \(M+1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le Q \le N\).
• \(1 \le X_i, Y_i \le N\) và \(X_i \ne Y_i\) với \(1 \le i \le N-1\).
• \(1 \le D_j \le N-1\) với \(1 \le j \le M\).
• \(1 \le C_k \le N\) với \(1 \le k \le Q\).
• Các giá trị \(C_k\) đôi một khác nhau.
• Nếu tất cả các đường truyền đều hoạt động, có thể đi từ một máy chủ bất kỳ đến mọi máy chủ khác qua các đường truyền.

Chấm điểm

• Subtask 1 (\(30\) điểm): \(Q = 1\).
• Subtask 2 (\(30\) điểm): \(X_i = i\) và \(Y_i = i+1\) với mọi \(1 \le i \le N-1\).
• Subtask 3 (\(40\) điểm): Không có ràng buộc bổ sung.

5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5

3
5
4

Giả sử ban đầu máy chủ \(i\) chứa mẩu thông tin \(i\) với \(1 \le i \le 5\).

• Tại thời điểm \(1\), đường truyền \(1\) được xây dựng, nối máy chủ \(1\) và \(2\). Sau khi đồng bộ hóa, cả hai máy chủ đều chứa các mẩu thông tin \(1, 2\).
• Tại thời điểm \(2\), đường truyền \(2\) được xây dựng, nối máy chủ \(1\) và \(3\). Cùng với đường truyền \(1\), ba máy chủ \(1, 2, 3\) được kết nối với nhau và đều chứa các mẩu thông tin \(1, 2, 3\).
• Tại thời điểm \(3\), đường truyền \(1\) ngừng hoạt động vì nó đang hoạt động ngay trước thời điểm này.
• Tại thời điểm \(4\), đường truyền \(4\) được xây dựng, nối máy chủ \(2\) và \(5\). Cả hai máy chủ đều chứa các mẩu thông tin \(1, 2, 3, 5\). Máy chủ \(1\) và \(2\) không thể trao đổi thông tin vì đường truyền \(1\) đã ngừng hoạt động.
• Tại thời điểm \(5\), đường truyền \(4\) ngừng hoạt động.
• Tại thời điểm \(6\), đường truyền \(3\) được xây dựng, nối máy chủ \(2\) và \(4\). Cả hai máy chủ đều chứa các mẩu thông tin \(1, 2, 3, 4, 5\).

Vì vậy, vào cuối quá trình, các máy chủ \(1, 4, 5\) lần lượt chứa \(3, 5, 4\) mẩu thông tin khác nhau.

Úc có nhiều nét văn hóa thú vị, với các môn thể thao và các loài động vật đa dạng. Bạn muốn theo dõi nhiều sự kiện được tổ chức trên một con đường ở Brisbane.

Con đường được chia thành \(1\,000\,000\,000\) đoạn, đánh số từ \(1\) đến \(1\,000\,000\,000\) theo thứ tự từ tây sang đông. Có \(N\) sự kiện bạn muốn theo dõi; sự kiện thứ \(i\) diễn ra tại đoạn \(A_i\).

Để theo dõi các sự kiện, bạn đã chuẩn bị \(P\) máy ảnh nhỏ và \(Q\) máy ảnh lớn. Bạn có thể chọn một số nguyên dương \(w\) làm tham số chụp ảnh. Khi đó, mỗi máy ảnh nhỏ có thể chụp tối đa \(w\) đoạn liên tiếp, còn mỗi máy ảnh lớn có thể chụp tối đa \(2w\) đoạn liên tiếp. Một đoạn đường có thể được nhiều máy ảnh cùng chụp.

Bạn muốn chụp được tất cả các đoạn đường có sự kiện. Vì dự kiến có nhiều người đến tham dự, để bảo đảm an toàn, vị trí của các máy ảnh phải được cố định và không được di chuyển trong suốt thời gian diễn ra các sự kiện. Giá trị \(w\) càng lớn thì chi phí chụp ảnh càng cao, nên bạn muốn chọn \(w\) nhỏ nhất có thể.

Yêu cầu

Cho vị trí các sự kiện và số lượng máy ảnh của mỗi loại, hãy tìm số nguyên dương \(w\) nhỏ nhất sao cho có thể chụp được tất cả các đoạn đường có sự kiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, P, Q\) cách nhau bởi dấu cách, lần lượt là số sự kiện, số máy ảnh nhỏ và số máy ảnh lớn.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(A_i\), là số hiệu đoạn đường diễn ra sự kiện thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là giá trị nhỏ nhất của \(w\) sao cho có thể chụp được tất cả các đoạn đường có sự kiện.

Ràng buộc

• \(1 \le N \le 2\,000\).
• \(1 \le P \le 100\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Chấm điểm

• Subtask 1 (\(50\) điểm): \(N \le 100\).
• Subtask 2 (\(50\) điểm): Không có ràng buộc bổ sung.

3 1 1
2
11
17

4

Khi chọn \(w = 4\), bạn có thể chụp được tất cả các đoạn đường có sự kiện. Chẳng hạn, dùng máy ảnh nhỏ để chụp các đoạn từ \(1\) đến \(3\) và máy ảnh lớn để chụp các đoạn từ \(11\) đến \(18\).

13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75

9