CHO ĐỘI TUYỂN HSG

Đề xuất 10 chuyên
Phân công 2 người (SCHE2N)
Có 2𝑁 việc đánh số 1, 2, ..., 2𝑁 cần được phân công cho hai người, mỗi người 𝑁 việc. Thời gian làm việc 𝑖 của người thứ nhất và người thứ hai tương ứng là
𝑎
𝑖,
𝑏
𝑖.
Hãy xác định tổng thời gian hoàn thành toàn bộ 2𝑁 việc nhỏ nhất có thể.
Dữ liệu
Dòng 1: số nguyên dương 𝑁 (𝑁≤4
10
5)
Dòng 2...2𝑁+1: dòng 𝑖+1 ghi hai số nguyên dương 𝑎_𝑖,
𝑏
𝑖
𝑎
𝑖,
𝑏
𝑖≤100

Kết quả
Dòng 1: số nguyên là tổng thời gian hai người làm hết 2𝑁 việc nhỏ nhất có thể.
Ví dụ
sche2n.inp
sche2n.out

2
2 1
3 2
5 3
1 2
8


Đo độ lớn (VALMETRIC)
Cho dãy số nguyên
𝑎
1
𝑎
2
𝑎
𝑁. Ta định nghĩa độ lớncủa mỗi phần tử
𝑎
𝑖
1≤𝑖≤𝑁 là số lượng phần tử trong dãy nhỏ hơn
𝑎
𝑖.
Hãy xác định đoạn 𝐾 phần tử liên tiếp của dãy có tổng độ lớn là lớn nhất.
Dữ liệu
Dòng 1: hai số nguyên 𝑁, 𝐾
1≤𝐾≤𝑁
10
5

Dòng 2: 𝑁 số nguyên
𝑎
1
𝑎
2
𝑎
𝑁
1
𝑎
𝑖
10
9 ∀𝑖

Kết quả
Dòng 1: số nguyên là chỉ số phần tử bắt đầu của đoạn tìm được, nếu có nhiều nghiệm thì chọn đoạn trái nhất.
Ví dụ
valmetric.inp
valmetric.out

4 2
1 2 2 1
2


Hình chữ nhật con (SRECMAXP)
Cho lưới ô vuông kích thước 𝑀×𝑁, các hàng đánh số 1…𝑀 từ trên xuống, các cột đánh số 1…𝑁 từ trái sang, ô (𝑖,𝑗) chứa kí tự ‘.’ hoặc ‘𝑋’ thể hiện ô là trống hay có vật cản.
Hãy xác định chu vi lớn nhất có thể của một hình chữ nhật con cạnh song song với cạnh lưới gồm toàn các ô trống.
Dữ liệu
Dòng 1: hai số nguyên 𝑀, 𝑁 (1≤𝑀,𝑁≤400)
Dòng 2…𝑀+1: dòng 𝑖+1 ghi xâu độ dài 𝑁 thể hiện hàng 𝑖 của lưới.
Kết quả
Dòng 1: số nguyên là chu vi lớn nhất có thể.
Ví dụ
srecmaxp.inp
srecmaxp.out

4 4
X.XX
X..X
..X.
..XX
10