BOI 2016 - Ngày 2

Byteland có \(n\) thành phố, trong đó có \(k\) thành phố quan trọng mà nhà vua thường xuyên ghé thăm.

Đất nước còn có \(m\) con đường, mỗi con đường nối hai thành phố. Đáng tiếc là tình trạng đường sá quá tệ, khiến nhà vua không thể lái chiếc xe thể thao của mình trên những con đường đó với tốc độ tối đa.

Chi phí sửa chữa từng con đường đã được biết trước. Nhiệm vụ của bạn là chọn những con đường cần sửa chữa sao cho tất cả \(k\) thành phố quan trọng được kết nối với nhau bằng các con đường đã sửa chữa, đồng thời tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(m\): số thành phố, số thành phố quan trọng và số con đường. Các thành phố được đánh số \(1,2,\ldots,n\).

Dòng thứ hai chứa \(k\) số nguyên: số hiệu các thành phố quan trọng.

Cuối cùng là \(m\) dòng mô tả các con đường. Mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\), cho biết có một con đường hai chiều nối thành phố \(a\) với thành phố \(b\), và chi phí sửa chữa con đường đó là \(c\).

Dữ liệu bảo đảm tồn tại đường đi giữa hai thành phố bất kỳ.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để sửa chữa các con đường sao cho nhà vua có thể di chuyển giữa tất cả các thành phố quan trọng bằng chiếc xe thể thao của mình.

Ràng buộc

Trong mọi phân nhóm, \(1 \le c \le 10^9\) và \(n \ge k\).

Phân nhóm

1. Nhóm 1 (22 điểm): \(2 \le k \le 5\); \(n \le 20\); \(1 \le m \le 40\).
2. Nhóm 2 (14 điểm): \(2 \le k \le 3\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).
3. Nhóm 3 (15 điểm): \(2 \le k \le 4\); \(n \le 1000\); \(1 \le m \le 2000\).
4. Nhóm 4 (23 điểm): \(k=4\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).
5. Nhóm 5 (26 điểm): \(k=5\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).

Ví dụ

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

11

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài A.

Uolevi đã phát triển một trò chơi trong đó người chơi thu thập tiền xu trong mê cung. Hiện tại, vấn đề là trò chơi quá dễ. Bạn có thể thiết kế những mê cung đầy thử thách cho trò chơi này không?

Mỗi mê cung là một bảng ô vuông hình chữ nhật gồm các ô sàn (.) và các ô tường (#). Một ô là căn cứ (x), và một số ô có thể chứa tiền xu (o). Người chơi bắt đầu tại căn cứ và có thể di chuyển sang trái, sang phải, lên trên hoặc xuống dưới, mỗi bước sang một ô kề cạnh không phải tường và nằm trong mê cung. Nhiệm vụ của người chơi là thu thập tất cả tiền xu trong mê cung rồi quay về căn cứ.

Độ khó của một mê cung là độ dài của đường đi ngắn nhất bắt đầu tại căn cứ, thu thập tất cả tiền xu và quay về căn cứ. Độ dài được tính bằng số bước di chuyển.

Dữ liệu vào

Dữ liệu bắt đầu bằng số nguyên \(t\): số mê cung. Tiếp theo là \(t\) dòng, mỗi dòng chứa ba số nguyên \(n\), \(m\) và \(k\). Mê cung tương ứng phải có kích thước \(n \times m\) ô và chứa đúng \(k\) tiền xu.

Dữ liệu ra

In ra \(t\) mô tả mê cung theo đúng thứ tự trong dữ liệu vào, ngăn cách các mê cung bằng dòng trống. Mỗi mô tả gồm \(n\) dòng, mỗi dòng có đúng \(m\) ký tự, không có dấu cách giữa các ký tự. Chỉ được sử dụng các ký tự ., #, x và o; mỗi mê cung phải có đúng một ký tự x và đúng \(k\) ký tự o.

Mỗi mê cung phải giải được: từ căn cứ, người chơi phải có thể thu thập tất cả tiền xu rồi quay về căn cứ. Các ô sàn không chứa tiền xu có thể nằm ngoài thành phần liên thông của căn cứ.

Nộp bài

Đây là bài chỉ nộp kết quả (output-only), với duy nhất một tệp dữ liệu vào maze.in. Bạn có thể tải tệp dữ liệu vào maze.in. Bạn phải nộp một tệp kết quả maze.out chứa tất cả các mê cung được yêu cầu trong tệp dữ liệu vào.

Ràng buộc

Tệp maze.in chứa \(t=50\) mê cung. Các kích thước và số tiền xu thỏa mãn \(2 \le n,m \le 20\) và \(1 \le k \le 12\).

Chấm điểm

• Trình chấm kiểm tra kích thước, các ký tự, số căn cứ, số tiền xu và khả năng giải được của từng mê cung. Nếu bất kỳ mê cung nào không hợp lệ hoặc không giải được, toàn bộ bài nộp nhận \(0\) điểm.

• Với mỗi mê cung hợp lệ, điểm của bạn là:

  \[ \max\bigl(0,\ 100-3(d-x)\bigr), \]

  trong đó \(x\) là độ khó của mê cung bạn tạo ra, còn \(d\) là độ khó của mê cung khó nhất mà ban giám khảo tìm được cho cùng yêu cầu. Công thức này không chặn điểm ở \(100\) nếu \(x>d\).

• Tổng điểm của bài là trung bình cộng điểm của tất cả các mê cung, làm tròn xuống số nguyên:

  \[ \left\lfloor \frac{1}{t}\sum_{i=1}^{t}\max\bigl(0,\ 100-3(d_i-x_i)\bigr) \right\rfloor. \]

Ví dụ

2
3 3 1
4 7 2

###
#.x
#o#

.o.####
.#..x.#
...##.#
###o...

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài B.

Bạn được cho một dãy gồm \(n\) số \(x_1,x_2,\ldots,x_n\). Mỗi số \(1,2,\ldots,n\) xuất hiện đúng một lần trong dãy.

Bạn có thể thay đổi dãy bằng các phép đổi chỗ. Có \(n-1\) lượt liên tiếp, được đánh số \(k=2,3,\ldots,n\). Ở lượt \(k\), bạn có thể đổi chỗ hai giá trị \(x_k\) và \(x_{\lfloor k/2 \rfloor}\) trong dãy hoặc không làm gì.

Dãy \(a_1,a_2,\ldots,a_n\) nhỏ hơn dãy \(b_1,b_2,\ldots,b_n\) theo thứ tự từ điển nếu tồn tại một chỉ số \(j\) (\(1 \le j \le n\)) sao cho \(a_k=b_k\) với mọi \(k<j\) và \(a_j<b_j\).

Hãy tìm dãy nhỏ nhất theo thứ tự từ điển mà bạn có thể thu được.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên: các số trong dãy.

Dữ liệu ra

In ra \(n\) số nguyên biểu diễn dãy nhỏ nhất theo thứ tự từ điển có thể thu được.

Phân nhóm

1. Nhóm 1 (10 điểm): \(1 \le n \le 20\).
2. Nhóm 2 (11 điểm): \(1 \le n \le 40\).
3. Nhóm 3 (27 điểm): \(1 \le n \le 1000\).
4. Nhóm 4 (20 điểm): \(1 \le n \le 5 \cdot 10^4\).
5. Nhóm 5 (32 điểm): \(1 \le n \le 2 \cdot 10^5\).

Ví dụ

5
3 4 2 5 1

2 1 3 4 5

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài C.