JOI 2010 Final Camp - Ngày 3

Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(M\) con đường. Mỗi con đường nối hai thành phố khác nhau và có thể đi theo cả hai chiều. Từ bất kỳ thành phố nào cũng có thể đi đến bất kỳ thành phố nào khác bằng các con đường này. Tất cả các con đường ở JOI đều là đường thu phí, và mỗi con đường có một mức phí riêng.

Đất nước JOI cũng tổ chức Olympic Tin học. Mỗi thành phố cử một thí sinh đại diện tham dự vòng chung kết. Cần quyết định những thành phố sẽ tổ chức vòng chung kết và ước tính chi phí đưa các thí sinh đến đó. Vòng chung kết được tổ chức tại \(K\) thành phố; khi vòng chung kết diễn ra, mọi thí sinh phải có mặt tại một trong các thành phố được chọn. Không có giới hạn về số thí sinh tập trung tại một thành phố.

Các thí sinh sử dụng đường bộ để đến nơi tổ chức vòng chung kết. Với một con đường có mức phí \(c\), dù có bao nhiêu người cùng đi qua trong một lượt thì phí của lượt đó vẫn là \(c\). Vì vậy, có thể tiết kiệm chi phí bằng cách sắp xếp thứ tự di chuyển để nhiều thí sinh cùng đi qua một con đường trong một lượt.

Yêu cầu

Hãy chọn các thành phố tổ chức vòng chung kết và cách đưa các thí sinh đến đó sao cho tổng phí đường bộ phải trả là nhỏ nhất. Cho \(N,M,K\) và thông tin về tất cả các con đường, hãy viết chương trình tính tổng phí nhỏ nhất này.

Dữ liệu vào

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

• Dòng đầu chứa ba số nguyên \(N,M,K\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) mô tả con đường thứ \(i\), gồm ba số nguyên \(A_i,B_i,C_i\), cách nhau bởi dấu cách. Con đường này nối hai thành phố \(A_i\) và \(B_i\), có mức phí \(C_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng phí nhỏ nhất để đưa tất cả các thí sinh đến các thành phố tổ chức vòng chung kết.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le100\,000\): số thành phố.

• \(1\le M\le100\,000\): số con đường.
• \(1\le K\le N\): số thành phố tổ chức vòng chung kết.
• \(1\le A_i<B_i\le N\) với \(1\le i\le M\).
• \(1\le C_i\le100\) với \(1\le i\le M\).
• Từ bất kỳ thành phố nào cũng có thể đi đến bất kỳ thành phố nào khác bằng đường bộ.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) nhóm kiểm thử, mỗi nhóm \(10\) điểm. Có tất cả \(12\) bộ dữ liệu: hai nhóm có \(2\) bộ dữ liệu mỗi nhóm, tám nhóm còn lại có \(1\) bộ dữ liệu mỗi nhóm. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên tất cả các bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

Các nhóm test dưới đây có thể chồng lấp:

• Các nhóm test có tổng cộng \(40\) điểm thỏa mãn \(N\le1\,000\).
• Các nhóm test có tổng cộng \(40\) điểm thỏa mãn \(K=1\).
• Các nhóm test có tổng cộng \(20\) điểm thỏa mãn đồng thời \(N\le1\,000\) và \(K=1\).
• Các nhóm test có tổng cộng \(60\) điểm thỏa mãn ít nhất một trong hai điều kiện \(N\le1\,000\) hoặc \(K=1\).

Ví dụ

4 3 1
1 2 2
2 3 9
2 4 5

16

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

12

Bạn có một trò chơi điện tử do công ty JOI phát hành. Trò chơi được làm khá tốt, và bạn vẫn vui vẻ chơi mỗi ngày.

Một ngày nọ, một màn chơi được các game thủ gọi là “trốn tìm” xuất hiện. Có vẻ màn chơi này có lỗi, khiến ngay cả những người chơi giỏi cũng chỉ có xác suất vượt qua rất nhỏ.

Sau nhiều lần thử sức, bạn nhận ra rằng mình có thể vượt qua màn chơi nếu đưa ra quyết định thật nhanh, và nghĩ đến việc viết chương trình để làm điều đó.

Màn trốn tìm diễn ra trên một khu vực có nhiều chướng ngại vật. Khu vực này là một hình chữ nhật được chia thành các ô vuông \(1\times1\). Mỗi ô được biểu diễn bằng một cặp số nguyên \((x,y)\), với \(1\le x\le100\,000\) và \(1\le y\le1\,000\,000\,000\). Ô \((1,1)\) nằm ở góc trên bên trái; ô \((x+1,y+1)\) là ô cách ô \((1,1)\) một khoảng \(x\) ô về bên phải và \(y\) ô xuống dưới.

Mỗi chướng ngại vật chiếm \(w\) ô liên tiếp có cùng tọa độ \(y\), tạo thành một hình chữ nhật gồm \(w\times1\) ô. Một chướng ngại vật được mô tả bằng tọa độ \((x,y)\) của ô có tọa độ \(x\) nhỏ nhất trong nó và độ dài \(w\). Các chướng ngại vật chỉ nằm ở những ô có \(y\ge2\), và không có hai chướng ngại vật nào chồng lên nhau.

Khi màn chơi bắt đầu, người chơi di chuyển quanh khu vực. Người chơi có thể đến bất kỳ ô nào, kể cả ô có chướng ngại vật.

Sau một khoảng thời gian nhất định, kẻ địch xuất hiện và tấn công. Khi đó, người chơi bắt buộc phải ẩn mình trong một chướng ngại vật: chỉ cần đứng ở một ô có chướng ngại vật là đã ẩn mình trong đó. Nếu chọn được chướng ngại vật thích hợp, người chơi sẽ tránh được đòn tấn công và có cơ hội phản công. Tận dụng cơ hội này sẽ giúp vượt qua màn chơi.

Kẻ địch có \(M\) loại vũ khí, chẳng hạn như súng ngắn, súng trường, pháo không giật, súng điện từ, v.v. Các vũ khí được đánh số riêng biệt từ \(1\) đến \(M\). Vũ khí thứ \(i\) có sức tấn công \(a_i\), nghĩa là nó có thể phá hủy số chướng ngại vật bằng giá trị đó. Nếu người chơi đang ẩn mình trong một chướng ngại vật bị phá hủy thì sẽ chịu sát thương.

Theo thiết kế ban đầu, kẻ địch sẽ chọn ngẫu nhiên một giá trị \(x\), xuất hiện ở ô \((x,1)\), rồi dùng một vũ khí được chọn ngẫu nhiên để tấn công xuống dưới. Tuy nhiên, do lỗi của trò chơi, kẻ địch luôn chọn đúng tọa độ \(x\) của người chơi và tấn công thẳng về phía người chơi.

Bạn quyết định dùng chương trình tự viết để tìm chỗ ẩn nấp tối ưu riêng cho từng vũ khí, nhằm có thể ứng phó với bất kỳ vũ khí nào kẻ địch sử dụng. Trong các chỗ ẩn nấp giúp tránh được đòn tấn công, chỗ tối ưu là chỗ có tọa độ \(y\) nhỏ nhất, để người chơi dễ phản công. Nếu có nhiều chỗ như vậy, chọn chỗ có tọa độ \(x\) nhỏ nhất.

Yêu cầu

Cho thông tin về các chướng ngại vật và sức tấn công của từng vũ khí, hãy viết chương trình tìm chỗ ẩn nấp tối ưu cho mỗi vũ khí. Nếu dù ẩn nấp ở đâu cũng bị tấn công, hãy xuất \((-1,-1)\) để biểu thị rằng không có chỗ ẩn nấp.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách, lần lượt là số chướng ngại vật và số loại vũ khí.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i,y_i,w_i\), cách nhau bởi dấu cách, mô tả chướng ngại vật thứ \(i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(a_j\), là sức tấn công của vũ khí thứ \(j\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(M\) dòng. Dòng thứ \(j\) chứa hai số nguyên \(x_j,y_j\), cách nhau bởi dấu cách, là tọa độ của chỗ ẩn nấp tối ưu khi kẻ địch sử dụng vũ khí thứ \(j\). Nếu không có chỗ nào tránh được đòn tấn công của vũ khí này, ghi -1 -1.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le50\,000\): số chướng ngại vật.

• \(1\le M\le50\,000\): số loại vũ khí.
• \(1\le x_i\le100\,000\): tọa độ \(x\) nhỏ nhất trong các ô của chướng ngại vật thứ \(i\).
• \(2\le y_i\le1\,000\,000\,000\): tọa độ \(y\) của chướng ngại vật thứ \(i\).
• \(1\le w_i+x_i-1\le100\,000\), trong đó \(w_i\) là độ dài của chướng ngại vật thứ \(i\).
• \(1\le a_j\le N\): sức tấn công của vũ khí thứ \(j\).
• Các chướng ngại vật không chồng lên nhau.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) nhóm kiểm thử, mỗi nhóm \(10\) điểm và chứa \(2\) bộ dữ liệu, tổng cộng \(20\) bộ dữ liệu. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên cả hai bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

• Các nhóm test có tổng cộng \(30\) điểm thỏa mãn \(x_i+w_i-1\le10\,000\) với mọi \(1\le i\le N\), đồng thời \(N\le1\,000\).

Ví dụ

13 2
2 2 10
14 3 9
15 6 12
3 7 5
16 8 9
15 10 3
4 13 10
11 11 11
5 4 11
11 14 12
6 9 7
20 4 8
13 5 5
4
7

15 10
-1 -1

Công ty JOI bán một trò chơi mô phỏng mang tên SimRoad. Trong trò chơi này, người chơi trở thành người cai trị một đất nước và thực hiện nhiều công việc để giúp đất nước phát triển thịnh vượng.

Đất nước trong trò chơi đang ở thời nguyên thủy. Các khu dân cư nằm rải rác, nhưng phần lớn đất đai bị cỏ cao bao phủ nên việc đi lại giữa các khu dân cư rất khó khăn. Nhiệm vụ đầu tiên của bạn là cắt cỏ để cư dân có thể dễ dàng đi lại giữa các khu dân cư.

Đất nước được chia thành một lưới gồm \(W\) ô theo hướng đông–tây và \(H\) ô theo hướng bắc–nam. Mỗi ô có một trong ba trạng thái: w nghĩa là ô bị cỏ bao phủ, . nghĩa là ô đất trống không có cỏ, còn @ nghĩa là ô có một khu dân cư.

Yêu cầu

Cư dân có thể tự do di chuyển đến ô kề bên theo một trong bốn hướng đông, tây, nam, bắc nếu ô đó là khu dân cư hoặc đất trống, nhưng không thể đi vào ô bị cỏ bao phủ. Bạn phải cắt cỏ ở một số ô để biến chúng thành đất trống, sao cho từ bất kỳ khu dân cư nào cũng có thể đi đến tất cả các khu dân cư khác.

Muốn cắt cỏ, bạn phải thuê cư dân làm việc; cắt cỏ ở một ô tốn \(1\) đô la. Để dành tiền cho sự phát triển về sau, bạn muốn chi tiêu càng ít càng tốt.

Có thể có nhiều cách cắt cỏ. Với trạng thái đất nước được cho, hãy tìm cách cắt cỏ ở càng ít ô càng tốt và tạo ra trạng thái đất nước sau khi cắt cỏ.

Đây là bài chỉ nộp kết quả (output-only). Bạn phải nộp các tệp kết quả cho năm tệp dữ liệu vào được cung cấp.

Thuật toán cơ bản

Đặt \(y'\) bằng \(H/2\) nếu \(H\) chẵn, và bằng \((H+1)/2\) nếu \(H\) lẻ:

Trước hết, cắt cỏ ở tất cả các ô bị cỏ bao phủ trên hàng thứ \(y'\) tính từ phía bắc. Sau đó, với mỗi khu dân cư, cắt hết cỏ trên đoạn theo hướng bắc–nam nối khu dân cư đó với ô ở hàng thứ \(y'\) tính từ phía bắc, trên cùng cột.

Dữ liệu vào

Có tất cả \(5\) tệp dữ liệu vào, mang tên simroad-ink.txt với \(k=1,2,3,4,5\), tức là simroad-in1.txt, simroad-in2.txt, simroad-in3.txt, simroad-in4.txt và simroad-in5.txt.

Tải bộ dữ liệu vào. Tệp ZIP gồm năm tệp 01.in, 02.in, 03.in, 04.in, 05.in, lần lượt tương ứng với simroad-in1.txt đến simroad-in5.txt trong đề.

Mỗi tệp có định dạng như sau:

• Dòng đầu chứa hai số nguyên \(W,H\), cách nhau bởi dấu cách.
• \(H\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(W\) ký tự, mô tả trạng thái đất nước. Ký tự thứ \(x\) trên dòng thứ \(y\) trong các dòng này là w, . hoặc @, biểu diễn trạng thái của ô thứ \(y\) tính từ phía bắc và thứ \(x\) tính từ phía tây.

Dữ liệu ra

Nộp dữ liệu ra dưới dạng tệp. Tên tệp là simroad-outk.txt với \(k=1,2,3,4,5\), tức là simroad-out1.txt, simroad-out2.txt, simroad-out3.txt, simroad-out4.txt và simroad-out5.txt. Tệp simroad-outk.txt phải chứa kết quả tương ứng với tệp simroad-ink.txt.

Mỗi tệp kết quả mô tả trạng thái đất nước sau khi cắt cỏ, gồm \(H\) dòng, mỗi dòng có đúng \(W\) ký tự. Ký tự thứ \(x\) trên dòng thứ \(y\) phải là w, . hoặc @, biểu diễn trạng thái của ô thứ \(y\) tính từ phía bắc và thứ \(x\) tính từ phía tây.

Chỉ được thay các ô w đã cắt cỏ bằng .; các ô khác giữ nguyên trạng thái. Không ghi dòng kích thước \(W,H\) vào tệp kết quả.

Ràng buộc

• \(1\le W\le100\): số ô theo hướng đông–tây.
• \(1\le H\le100\): số ô theo hướng bắc–nam.

Phân nhóm

• Có \(5\) bộ dữ liệu, mỗi bộ tối đa \(20\) điểm, tổng cộng \(100\) điểm.

Điểm của mỗi bộ dữ liệu phụ thuộc vào trạng thái đất nước trong tệp kết quả bạn nộp. Nếu kết quả không đáp ứng yêu cầu của bài toán thì bạn nhận \(0\) điểm cho bộ dữ liệu đó. Nếu kết quả đáp ứng yêu cầu, điểm được tính như sau.

Gọi:

• \(E_y\) là số tiền cần chi để tạo ra trạng thái đất nước trong kết quả bạn nộp.
• \(E_b\) là số tiền cần chi để tạo ra trạng thái đất nước do thuật toán cơ bản sinh ra.
• \(E_m\) là số tiền nhỏ nhất cần chi để tạo ra một trạng thái đất nước trong các kết quả do các thí sinh tham gia kỳ thi nộp.

Giá trị dùng để tính điểm là:

Điểm của bạn là giá trị trên được làm tròn đến một chữ số sau dấu phẩy: xét chữ số thứ hai sau dấu phẩy, nếu chữ số đó từ \(5\) trở lên thì làm tròn lên, nếu nhỏ hơn \(5\) thì làm tròn xuống.

Ví dụ

7 5
w@ww@w@
w.wwwww
wwww@ww
@wwwwww
ww@.@w.

w@..@.@
w.ww.ww
wwww@ww
@www.ww
..@.@w.

w@ww@w@
w.ww.w.
....@..
@w.w.ww
ww@.@w.