HSG lớp 9 Đà Nẵng 2019-2020

ĐỀ THI HỌC SINH GIỎI LỚP 9 THÀNH PHỐ ĐÀ NẴNG Năm 2020

MÔN TIN HỌC 3 bài: CAPDOI, XAUDX, TSNT

---

Ghi chú

Tài liệu sưu tầm chỉ ghi “2020 HSG9 DANANG”, đề được đánh máy lại (không có phần tiêu đề gốc của Sở GD&ĐT). Bài 1 không ghi tên tệp vào/ra.

Bài 1. CAPDOI - Đếm cặp đôi

Cho dãy số A gồm n phần tử nguyên dương A₁, A₂, …, Aₙ. Mỗi phần tử có giá trị không vượt quá 10⁹ và n ≤ 10⁵. Một cặp số được gọi là cặp tương đồng với x, nếu cặp số này có tổng bằng số x cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số A có bao nhiêu cặp số (Aᵢ; Aⱼ) tương đồng với x (có nghĩa là Aᵢ + Aⱼ = x) với i < j.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số n, x (n ≤ 10⁵, x ≤ 10⁶).
• Dòng thứ 2 chứa n phần tử của dãy số A (Aᵢ ≤ 10⁹).

Kết quả: Ghi ra một số nguyên là số cặp đôi tương đồng của dãy số.

Input	Output
7 6 1 2 4 3 4 5 3	4

Bài 2. XAUDX - Xâu đối xứng

Cho một xâu ký tự S chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: madam, ioi là các xâu đối xứng.

Yêu cầu: Với xâu ký tự S cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Dữ liệu vào: Đọc từ file văn bản XAUDX.INP chứa một xâu ký tự S có n ký tự (n ≤ 10⁵) chỉ gồm các ký tự chữ cái thường a..z.

Kết quả: Ghi ra file văn bản XAUDX.OUT một số nguyên là số lượng ký tự ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Input	Output
aammmda	2
aaabbcc	0

Ràng buộc:

• Subtask 1: chiếm 30% số điểm của bài toán chỉ chứa 2 ký tự a và b.
• Subtask 2: chiếm 30% số điểm của bài toán chỉ chứa 3 loại ký tự bất kỳ.
• Subtask 3: chiếm 40% số điểm của bài toán với trường hợp còn lại.

Bài 3. TSNT - Thừa số nguyên tố

Cho dãy số A gồm n phần tử nguyên dương A₁, A₂, …, Aₙ. Hãy loại một phần tử bất kỳ trong dãy số và đặt P tích các số còn lại. Phân tích thừa số nguyên tố của P, sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm 4 số 1; 2; 4; 10 có 2 cách bỏ đều cho tổng số mũ bằng 3 là nhỏ nhất:

• Cách 1: Loại bỏ số 4, ta có P = 1 × 2 × 10 = 20 = 2² × 5 có tổng số mũ bằng 3.
• Cách 2: Loại bỏ số 10, ta có P = 1 × 2 × 4 = 8 = 2³ có tổng số mũ bằng 3.

Yêu cầu: Cho dãy số A, hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Dữ liệu vào: Đọc từ file văn bản TSNT.INP:

• Dòng đầu tiên chứa số n (n ≤ 10⁵).
• Dòng thứ 2 chứa n phần tử của dãy số A (Aᵢ ≤ 10⁶).

Dữ liệu ra: Ghi ra file văn bản TSNT.OUT một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input	Output
4 1 2 4 10	3

Ràng buộc:

• Subtask 1: chiếm 30% số điểm của bài toán có N ≤ 10⁴ và Aᵢ ≤ 3.
• Subtask 2: chiếm 30% số điểm của bài toán có N ≤ 10⁴ và Aᵢ ≤ 8.
• Subtask 3: chiếm 30% số điểm của bài toán có N ≤ 10⁴ và Aᵢ ≤ 10⁶.
• Subtask 4: chiếm 10% số điểm của bài toán với trường hợp còn lại.