HSG10 Thái Nguyên 2026

HSG10 Thái Nguyên 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 số chung

Cho dãy A gồm n số nguyên dương a₁, a₂, ⋯, a_n. Một số nguyên dương g được gọi là ước số chung của dãy khi tất cả các phần tử trong dãy đều chia hết cho g.

Ví dụ: Với dãy A=[2,4,6,2,10] thì các số 1 và 2 là ước của tất cả các phần tử trong dãy. Vì vậy, số lượng ước chung của dãy A trong trường hợp này là 2.

Yêu cầu: Tìm số lượng ước số chung của tất cả các phần tử trong dãy A.

Input

• Dòng đầu tiên chứa số nguyên T (1 ≤ T ≤ 50) là số bộ dữ liệu vào. Theo sau là các bộ dữ liệu vào, mỗi bộ dữ liệu vào gồm 2 dòng:

• Dòng 1 chứa một số nguyên n (1 ≤ n ≤ 10²) là số phần tử của dãy A.

• Dòng 2 chứa n số nguyên dương a₁, a₂, ⋯, a_n (1 ≤ a_i ≤ 10⁶) là các phần tử của dãy A.

Output

Ứng với mỗi bộ dữ liệu vào, chương trình của bạn cần in ra một dòng chứa một số nguyên duy nhất là số lượng các ước số chung của tất cả các phần tử trong dãy A tương ứng.

Scoring

Sample Input 1

2
5
1 2 3 4 5
6
6 90 12 18 30 18

Sample Output 1

1
4

---

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. Truy vấn giá

Một siêu thị quản lý các mặt hàng đang kinh doanh bằng phần mềm quản lí trên máy tính, nhân viên trong siêu thị cần cập nhật giá bán (đơn vị: nghìn đồng) của các mặt hàng đang kinh doanh. Danh sách giá bán thay đổi liên tục khi siêu thị nhập thêm mặt hàng mới hoặc ngừng kinh doanh một mặt hàng. Ban quản lý thường xuyên cần truy vấn: mức giá thấp thứ k trong danh sách hiện tại là bao nhiêu?

Quy tắc xếp hạng như sau:

• Các mặt hàng có cùng giá được xếp cùng một mức.

• Mức tiếp theo tính theo số mức giá phân biệt thấp hơn nó cộng 1.

Yêu cầu: Xử lý n mặt hàng ban đầu và q thao tác theo thứ tự. Với mỗi thao tác truy vấn Q k, hãy cho biết mức giá thấp thứ k theo thứ hạng trong danh sách hiện tại. Nếu k lớn hơn số mức giá phân biệt hiện có, kết quả truy vấn là 0.

Input

• Dòng 1: số nguyên dương n là số mặt hàng ban đầu.

• Dòng 2: n số nguyên cách nhau bởi dấu cách là giá của n mặt hàng.

• Dòng 3: số nguyên dương q là số thao tác.

• q dòng tiếp theo, mỗi dòng ghi một thao tác theo một trong ba dạng:A x: nhập thêm một mặt hàng có giá x vào danh sách.D x: thực hiện loại bỏ duy nhất một mặt hàng có mức giá bằng x ra khỏi danh sách kinh doanh hiện tại. Trong trường hợp có nhiều mặt hàng cùng có giá x, chỉ xóa đi một đơn vị sản phẩm; các mặt hàng còn lại cùng mức giá này vẫn được giữ nguyên trong danh sách. Nếu tại thời điểm truy vấn không tồn tại mặt hàng nào có giá bằng x, hệ thống sẽ bỏ qua thao tác này và không thực hiện thay đổi nào.Q k: truy vấn mức giá thấp thứ k theo thứ hạng.

Output

Gồm nhiều dòng, với mỗi thao tác Q k ghi một dòng là kết quả của truy vấn tương ứng.

Scoring

Sample Input 1

4
5 3 3 7
8
Q 1
Q 2
A 4
Q 2
D 3
D 3
Q 2
Q 6

Sample Output 1

3
5
4
5
0

Notes

• Với Q 1: Truy vấn mức giá thấp thứ 1 cho giá trị 3.

• Với Q 2: Truy vấn mức giá thấp thứ 2 cho giá trị 5.

• Với A 4: Thêm 4 vào, danh sách thành: 5 3 3 7 4.

• Với Q 2: Truy vấn mức giá thấp thứ 2 cho giá trị 4.

• Với D 3: Xóa giá trị 3, danh sách thành 5 3 7 4.

• Với D 3: Xóa giá trị 3, danh sách thành 5 7 4.

• Với Q 2: Truy vấn mức giá thấp thứ 2 cho giá trị 5.

• Với Q 6: Truy vấn mức giá thấp thứ 6 (không tồn tại) cho giá trị 0.

---

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. Biến đổi số

Cho một số nguyên dương N. Ta thực hiện thao tác thay đổi các chữ số của N theo quy tắc sau:

• Chọn một vị trí bất kỳ trong chuỗi chữ số của N.

• Thay thế chữ số tại vị trí đó bằng một chữ số mới (từ 0 đến 9).

• Điều kiện: Số mới được tạo thành phải có cùng số lượng chữ số với N và không được có chữ số 0 ở đầu.

Mỗi lần thay đổi một vị trí được tính là một thao tác.

Yêu cầu: Hãy tìm số thao tác tối thiểu để biến đổi số N ban đầu thành một số mới là bội của 111.

Input

• Dòng 1: số nguyên T (1 ≤ T ≤ 25) là số lượng bộ dữ liệu.

• T dòng tiếp theo, mỗi dòng chứa một số nguyên dương N.

Output

Gồm T dòng tương ứng với kết quả của T bộ dữ liệu. Mỗi dòng là một số nguyên đại diện cho số thao tác tối thiểu tìm được hoặc -1 nếu không có phương án thỏa mãn.

Scoring

Sample Input 1

4
111
220
13
991990

Sample Output 1

0
1
-1
2

Notes

Có 4 bộ dữ liệu:

• Số 111 không cần biến đổi.

• Số 220 không chia hết cho 111. Ta có thể thay chữ số 0 ở cuối thành chữ số 2 để được số 222 chia hết cho 111.

• Số 13 không thể biến đổi để chia hết cho 111.

• Số 991990 cần biến đổi hai chữ số ở vị trí 3 và vị trí 6 để được số 999999 chia hết cho 111.

---

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. Năng lượng

Phi hành gia Tí đang thực hiện nhiệm vụ khám phá vũ trụ thì phi thuyền gặp sự cố cạn kiệt năng lượng. May mắn thay, Tí thu thập được một dãy gồm N tinh thể năng lượng xếp thành một hàng dọc, được đánh số thứ tự từ 1 đến N. Tí cần sử dụng toàn bộ số tinh thể này để nạp đầy cho K lõi động cơ của phi thuyền. Quy trình nạp năng lượng phải tuân thủ nghiêm ngặt các điều kiện sau để tránh phát nổ:

• Mỗi lõi động cơ phải được nạp bằng một dãy các tinh thể liên tiếp nhau.

• Toàn bộ N tinh thể đều phải được phân bổ hết vào K lõi động cơ.

• Để tránh quá tải, mỗi lõi động cơ không được chứa nhiều hơn M tinh thể.

• Mỗi tinh thể mang một mức điện tích nhất định (có thể là điện tích âm hoặc dương). Công suất hoạt động của một lõi động cơ được tính bằng giá trị tuyệt đối của tổng điện tích các tinh thể bên trong lõi đó.

• Tổng công suất cung cấp cho phi thuyền bằng tổng công suất của tất cả K lõi động cơ.

Yêu cầu: Bạn có trong tay danh sách mức điện tích của các tinh thể. Hãy giúp phi hành gia Tí tính toán cách chia tinh thể sao cho tổng công suất cung cấp cho phi thuyền là lớn nhất để có thể khởi hành về Trái đất an toàn.

Input

• Dòng đầu tiên chứa ba số nguyên N, K, M (1 ≤ N ≤ 3000, 1 ≤ M, K ≤ N).

• Dòng tiếp theo chứa N số nguyên A₁, A₂, ⋯, A_N (0 ≤ |A_i| ≤ 10⁹, 1 ≤ i ≤ N) thể hiện mức điện tích của từng tinh thể.

Output

Tổng công suất lớn nhất có thể đạt được.

Scoring

Sample Input 1

5 2 4
-7 -7 17 3 -20

Sample Output 1

26

Sample Input 2

3 2 2
-6 -15 13

Sample Output 2

34

Notes

Ví dụ 1: Cách chia tinh thể để tạo ra công suất lớn nhất:

• Lõi 1: (-7, -7, 17, 3), có công suất là |-7 - 7 + 17 + 3| = 6

• Lõi 2: (-20), có công suất là |-20| = 20

Tổng: 6 + 20 = 26

Ví dụ 2: Chia làm 2 lõi: (-6, -15) và (13)

Công suất là: |-6 - 15| + |13| = 34

---

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: Lời giải phụ thuộc cách hiểu đề; cần đối chiếu nguồn.