Luyện HSG
Điểm: 2
Câu 1(3.0 điểm): Giải nén xâu UNZIP.PAS
Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén dữ liệu dạng văn bản, ta sử dụng một phương pháp đơn giản được mô tả thông qua ví dụ sau: với xâu ký tự:
aaaabbb sẽ được nén lại thành xâu 4a3b
Cho một xâu ký tự St1 gồm các ký tự thuộ tập a..z. Gọi St là xâu nén của xâu St1 theo phương pháp được mô tả như trên. Xâu St gồm N (1 N 255) ký tự thuộc tập các ký tự: a..z, 0..9
Yêu cầu: Hãy giải nén xâu St để được xâu gốc St1.
Dữ liệu vào: Cho trong file văn bản UNZIP.INP có cấu trúc như sau:
- Dòng 1: Ghi xâu ký tự St.
Dữ liệu ra: Ghi ra file văn bản UNZIP.OUT theo cấu trúc như sau:
- Dòng 1: Ghi xâu St1 là xâu sau khi đã được giải nén.
Ví dụ:
UNZIP.INP UNZIP.OUT
12a5bk2c aaaaaaaaaaaabbbbbkcc
Câu 2 (3.0 điểm): Đường chạy địa hình ROUTE.PAS
Trong Đại hội thể thao Quốc tế, người ta dự định sẽ tổ chức một môn chạy bộ địa hình. Đường chạy địa hình là một đường khép kín, điểm bắt đầu cũng là điểm kết thúc. Đường chạy có độ dài N (mét), mỗi mét có một độ cao h (cm) so với mực nước biển.
Yêu cầu: Hãy đếm số lượng đường bằng, số lượng đường dốc lên và số lượng đường dốc xuống của đường chạy địa hình, tính từ điểm xuất phát.
Dữ liệu vào: Cho trong file văn bản ROUTE.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N, là chiều dài của đường chạy địa hình.
- Dòng 2: Ghi N số nguyên dương hi là độ cao của mét thứ i trên đường chạy địa hình. Các số được ghi cách nhau ít nhất một dấu cách (3 ≤ N ≤ 30000;
1 ≤ hi ≤ 30000).
Dữ liệu ra: Ghi ra file văn bản ROUTE.OUT theo cấu trúc như sau:
- Dòng 1: Ghi ba số nguyên dương x y z, trong đó x là số lượng đoạn đường bằng, y là số lượng đoạn đường dốc lên, z là số lượng đoạn đường dốc xuống của đường chạy địa hình. Các số được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
ROUTE.INP
6
20 23 60 50 50 20
ROUTER.OUT
2 1 2
Bạn là nhân viên tại một cửa hàng hoa, nơi cung cấp dịch vụ cắm hoa nghệ thuật. Bài toán được giao là:
Cửa hàng có ~n~ bông hoa khác nhau. Mỗi bông hoa ~i~ có:
- Chiều cao: ~h[i]~,
- Giá trị thẩm mỹ: ~v[i]~.
Ngoài ra, bạn có ~m~ chiếc lọ. Mỗi chiếc lọ ~j~ có chiều cao tối thiểu để có thể cắm bông hoa lên: ~l[j]~.
Yêu cầu:
- Mỗi bông hoa chỉ được sử dụng một lần.
- Mỗi lọ chỉ có thể cắm một bông hoa.
- Bông hoa ~i~ chỉ được cắm vào lọ ~j~ nếu ~h[i] >= l[j]~.
- Hãy tính tổng giá trị thẩm mỹ lớn nhất có thể đạt được.
Dữ liệu vào (Input):
- Dòng đầu tiên chứa hai số nguyên ~n~ ~(1 ≤ n ≤ 1000)~ và ~m~ ~(1 ≤ m ≤ 1000)~: số bông hoa và số chiếc lọ.
- Dòng thứ hai chứa ~n~ số nguyên: chiều cao của từng bông hoa ~(h[1], h[2], ..., h[n])~.
- Dòng thứ ba chứa ~n~ số nguyên: giá trị thẩm mỹ của từng bông hoa ~(v[1], v[2], ..., v[n])~.
- Dòng thứ tư chứa ~m~ số nguyên: chiều cao tối thiểu của từng lọ ~(l[1], l[2], ..., l[m])~.
Dữ liệu ra (Output):
In ra một số nguyên duy nhất: tổng giá trị thẩm mỹ lớn nhất.
Ví dụ:
Input
4 3
10 15 12 20
5 7 6 10
10 15 20
Output
22
Giải thích:
- Chọn bông hoa 1 (cao 10, giá trị 5) cho lọ 1 (yêu cầu cao ≥ 10).
- Chọn bông hoa 2 (cao 15, giá trị 7) cho lọ 2 (yêu cầu cao ≥ 15).
- Chọn bông hoa 4 (cao 20, giá trị 10) cho lọ 3 (yêu cầu cao ≥ 20).
- Tổng giá trị thẩm mỹ: 5 + 7 + 10 = 22.
Điểm: 2
Một thành phố có nhiều khu vực cần được kết nối với nhau thông qua các tuyến đường giao thông. Các tuyến đường này có chi phí xây dựng khác nhau, và mục tiêu của thành phố là xây dựng một mạng lưới giao thông sao cho tất cả các khu vực được kết nối và chi phí tổng thể là thấp nhất.
Tuy nhiên, một số tuyến đường giao thông có thể bị hư hỏng hoặc không thể xây dựng do các yếu tố địa lý. Thành phố muốn xây dựng mạng lưới giao thông sao cho tất cả các khu vực được kết nối với nhau, nhưng chỉ sử dụng các tuyến đường có chi phí xây dựng không vượt quá một mức nhất định.
Công ty giao thông muốn áp dụng thuật toán Kruskal để tìm cây khung nhỏ nhất (MST - Minimum Spanning Tree) để kết nối tất cả các khu vực với chi phí thấp nhất. Tuy nhiên, một ràng buộc bổ sung là các tuyến đường có chi phí lớn hơn một giá trị max_cost sẽ không được xem xét trong việc xây dựng mạng lưới.
Yêu cầu:
1. Đầu vào:
- Dòng đầu tiên chứa hai số nguyên
nvàm(3 ≤ n ≤ 1000, 1 ≤ m ≤ 10000), trong đó:nlà số lượng khu vực của thành phố.mlà số lượng tuyến đường giao thông có sẵn để kết nối các khu vực.
- Dòng thứ hai chứa một số nguyên
max_cost(1 ≤ max_cost ≤ 100000), là chi phí tối đa cho phép để xây dựng một tuyến đường giao thông mới. - Tiếp theo là
mdòng, mỗi dòng chứa 3 số nguyênu,v,c(1 ≤ u, v ≤ n, 1 ≤ c ≤ 100000), trong đó:uvàvlà hai khu vực có thể kết nối nhau qua tuyến đường giao thông.clà chi phí để xây dựng tuyến đường giao thông giữa khu vựcuvà khu vựcv.
Lưu ý: Các tuyến đường có chi phí lớn hơn max_cost sẽ không được xem xét trong quá trình xây dựng mạng lưới giao thông.
2. Đầu ra:
- In ra tổng chi phí thấp nhất để xây dựng mạng lưới giao thông sao cho tất cả các khu vực đều được kết nối với nhau và không sử dụng tuyến đường có chi phí vượt quá
max_cost. - Nếu không thể kết nối tất cả các khu vực (do không đủ tuyến đường hợp lệ), in ra "Không thể kết nối tất cả các khu vực".
Giải thích:
- Bạn cần áp dụng thuật toán Kruskal để tìm cây khung nhỏ nhất (MST). Tuy nhiên, chỉ các tuyến đường có chi phí nhỏ hơn hoặc bằng
max_costmới được xem xét trong quá trình tìm kiếm cây khung nhỏ nhất. - Nếu sau khi chạy thuật toán Kruskal, số lượng cạnh trong cây khung nhỏ nhất là ít hơn
n-1, điều đó có nghĩa là không thể kết nối tất cả các khu vực, và kết quả sẽ là "Không thể kết nối tất cả các khu vực".
Ví dụ:
Input:
5 7
7
1 2 5
1 3 10
1 4 3
2 3 2
2 4 9
3 4 6
3 5 7
Output:
18
Giải thích:
- Có 5 khu vực và 7 tuyến đường có sẵn. Tuy nhiên, chỉ những tuyến đường có chi phí nhỏ hơn hoặc bằng 7 mới được xem xét.
- Kết nối khu vực 1 với khu vực 4 (chi phí = 3).
- Kết nối khu vực 1 với khu vực 2 (chi phí = 5).
- Kết nối khu vực 2 với khu vực 3 (chi phí = 2).
- Kết nối khu vực 3 với khu vực 5 (chi phí = 7).
Tổng chi phí là 3 + 5 + 2 + 7 = 18.