HSG12 Tuyên Quang 2026

HSG12 Tuyên Quang 2026

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Cặp số chẵn

Cho một dãy a gồm n số nguyên không âm a₁, a₂, ..., a_n.

Yêu cầu: Viết chương trình đếm số lượng cách chọn ra trong dãy a hai phần tử sao cho tích của hai phần tử đó là một số chẵn.

Input

• Dòng 1: Chứa một số nguyên n (2 ≤ n ≤ 10⁶);

• Dòng 2: Chứa n số nguyên a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10¹⁸ với 1 ≤ i ≤ n), các số cách nhau bởi một dấu cách trống.

Output

Ghi ra một số nguyên duy nhất là số lượng cặp số thỏa mãn yêu cầu đề bài.

Sample Input 1

5
1 6 6 13 8

Sample Output 1

9

Subtasks

• Có 40% số test ứng 40% số điểm của bài với n ≤ 10³;

• Có 30% số test ứng 30% số điểm của bài với a_i chẵn (1 ≤ i ≤ n);

• 30% số test còn lại ứng 30% số điểm của bài không có thêm ràng buộc.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Tổng ước

Cho dãy số a gồm n số nguyên dương a₁, a₂, ..., a_n. Viết chương trình tính tổng các ước dương của mỗi phần tử trong dãy a.

Input

• Dòng 1: Chứa số nguyên dương n (n ≤ 10⁶);

• Dòng 2: Chứa n số nguyên dương a₁, a₂, ..., a_n (a_i ≤ 10⁶; 1 ≤ i ≤ n).

Output

Ghi ra gồm một dòng chứa n số nguyên, số thứ i là tổng các ước dương của phần tử a_i.

Sample Input 1

4
2 4 10 9

Sample Output 1

3 7 18 13

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có n = 1;

• Có 30% số test ứng với 30% số điểm của bài có 1 < n ≤ 10³;

• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Tương phản

Trong tiết học Mỹ thuật, Zin được cô giáo giao cho bài tập phối màu cho các đỉnh của p hình tam giác như sau: Zin được cung cấp n hình tròn được đánh số lần lượt từ 1 đến n.

Hình tròn thứ i có màu sắc được mã hóa thành một số nguyên a_i.

Đầu tiên Zin chọn ra 3 hình tròn để dán lên 3 đỉnh của tam giác thứ nhất, giả sử chọn các hình tròn có số thứ tự i, j, k (i < j < k) khi đó độ tương phản của tam giác thứ nhất bằng max(a_i, a_j, a_k) - min(a_i, a_j, a_k).

Sau đó, Zin chọn 3 hình tròn tiếp theo (từ hình tròn có số thứ tự lớn hơn k) để trang trí cho tam giác thứ 2.

Lặp đi lặp lại các thao tác trên cho đến khi trang trí đủ p hình tam giác. Độ tương phản của p hình tam giác là độ tương phản của hình tam giác có độ tương phản lớn nhất.

Yêu cầu: Hãy giúp Zin trang trí cho p hình tam giác để có độ tương phản là nhỏ nhất có thể.

Input

• Dòng 1: Chứa hai số nguyên n, p (3 ≤ n ≤ 500; 3 × p ≤ n);

• Dòng 2: Chứa n số nguyên a₁, a₂, ..., a_n (|a_i| ≤ 10⁹; 1 ≤ i ≤ n).

Output

Ghi ra một số nguyên duy nhất là độ tương phản nhỏ nhất có thể tìm được.

Sample Input 1

10 2
3 9 4 4 -7 13 -6 4 -5 1

Sample Output 1

2

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có 3 × p = n;

• Có 30% số test ứng với 30% số điểm của bài có p = 1;

• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Cứu trợ

Sau trận mưa lũ lớn, trung tâm cứu trợ đặt tại địa điểm số 1 cần vận chuyển hàng hóa đến khu vực bị cô lập nghiêm trọng nhất tại địa điểm số N.

Hệ thống giao thông gồm N địa điểm được đánh số từ 1 đến N và M con đường hai chiều nối các địa điểm. Mỗi con đường nối hai địa điểm u, v có chi phí vận chuyển là c và giới hạn tải trọng tối đa là w (tấn).

Do điều kiện cầu đường không đồng đều, nếu một con đường trong hành trình chỉ chịu được w (tấn) thì xe chỉ có thể vận chuyển tối đa w (tấn) theo hành trình đó. Vì vậy, tải trọng của một hành trình được xác định bằng giá trị nhỏ nhất trong các giới hạn tải trọng của các con đường thuộc hành trình.

Xe cứu trợ chỉ chọn một hành trình duy nhất từ địa điểm 1 đến địa điểm N. Hiệu quả của hành trình được xác định bởi: Hiệu quả = Tải trọng của hành trìnhTổng chi phí của hành trình

Yêu cầu: Hãy xác định hiệu quả lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa hai số nguyên N, M (2 ≤ N ≤ 1000; 1 ≤ M ≤ 1000);

• M dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương u, v, c, w (u, v ≤ N; u ≠ v; c, w ≤ 1000). Dữ liệu đảm bảo tồn tại ít nhất một đường đi từ 1 đến N.

Output

Ghi ra một số là 10⁶ lần giá trị hiệu quả lớn nhất, lấy phần nguyên (tức là làm tròn xuống nếu giá trị này không phải số nguyên).

Sample Input 1

3 3
1 2 2 4
2 3 5 3
1 3 15 2

Sample Output 1

428571

• Nếu đi theo tuyến đường 1 → 2 → 3 thì tải trọng tối đa bằng min(4, 3) = 3 và tổng chi phí là 2 + 5 = 7, hiệu quả đạt được là 37.

• Nếu đi theo tuyến đường 1 → 3 thì tải trọng tối đa bằng 2 và tổng chi phí bằng 15, hiệu quả đạt được là 215. Vậy hiệu quả lớn nhất là 37. Theo yêu cầu đề bài, kết quả là ⌊ 10⁶ × 37 ⌋ = 428571.

Subtasks

• Có 30% số test ứng 30% số điểm của bài có 2 ≤ N, M ≤ 100 và mọi con đường có w bằng nhau;

• Có 30% số test ứng 30% số điểm của bài có 2 ≤ N, M ≤ 100;

• 40% số test còn lại ứng 40% số điểm của bài không có thêm ràng buộc.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.