HSG lớp 9 Quảng Nam 2021-2022

ĐỀ THI HỌC SINH GIỎI LỚP 9 CẤP TỈNH TỈNH QUẢNG NAM Năm học 2021 - 2022

MÔN TIN HỌC 4 bài: SPOW, PALIN, COUNT, MARKET

---

Ghi chú

Đề được đánh máy lại theo tài liệu “50 đề thi HSG THCS” (không kèm phần tiêu đề, thời gian làm bài và thang điểm của đề gốc).

Bài 1. Tổng và lũy thừa

Cho hai số tự nhiên a và n (1 ≤ a, n ≤ 10⁹).

Yêu cầu: Gọi S là tổng của a và n, T là lũy thừa aⁿ. Hãy tính S và T.

Dữ liệu vào: Từ tệp văn bản SPOW.INP gồm một dòng chứa 2 số a và n (các số cách nhau ít nhất một dấu cách).

Kết quả: Ghi ra tệp văn bản SPOW.OUT gồm hai dòng: Dòng thứ nhất là S và dòng thứ hai là T (do S và T có thể lớn nên kết quả của bài toán chia dư cho 10⁹ + 7).

Ví dụ:

SPOW.INP	SPOW.OUT
2 3	5 8

Ràng buộc:

• Có 80% test tương ứng 80% số điểm với a và n ≤ 10⁶;
• Có 20% test còn lại tương ứng 20% số điểm với 10⁶ < a và n ≤ 10⁹.

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

Cho một xâu S chứa ít nhất một chữ cái in hoa (‘A’ .. ‘Z’) hoặc một chữ cái thường (‘a’ .. ‘z’) hoặc một chữ số (‘0’ .. ‘9’). Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau.

Ví dụ: Xâu ‘aBa’, ‘abba’, ‘ccccc’ là xâu đối xứng. Còn những xâu ‘acba’, ‘abA’, ‘lop09’ không phải là xâu đối xứng.

Yêu cầu: Cho xâu S (với |S| là độ dài của xâu), hãy cho biết xâu S có đối xứng không? Nếu có thì ghi “YES” ngược lại thì ghi là “NO”.

Dữ liệu vào: Từ tệp văn bản PALIN.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương T (T ≤ 10⁴) là số lượng xâu S;
• T dòng tiếp theo, mỗi dòng chứa một xâu S.

Kết quả: Ghi ra tệp văn bản PALIN.OUT gồm T dòng, mỗi dòng là kết quả tương ứng với mỗi xâu S, ghi ra “YES” nếu là xâu đối xứng hoặc “NO” nếu không phải là xâu đối xứng.

Ví dụ:

PALIN.INP	PALIN.OUT
2 aBa acba	YES NO

Ràng buộc:

• Có 60% test tương ứng 60% số điểm với |S| ≤ 255;
• Có 40% test còn lại tương ứng 40% số điểm với |S| ≤ 1000.

Bài 3. Đếm giá trị

Hưng có người bạn thân tên Hà. Hưng đang tìm cách giải một bài toán liên quan đến số tự nhiên và cần sự giúp đỡ của Hà. Thử thách lần này là một dãy gồm N số tự nhiên bất kỳ nằm trong đoạn từ 0 tới 10⁷. Vấn đề đặt ra của bài toán là đếm số lượng giá trị khác nhau có trong dãy số và đưa ra số lần lặp của giá trị xuất hiện nhiều nhất. Vì số lượng các số tự nhiên trong dãy số đã cho có thể lên tới 10⁷ phần tử nên không thể đếm thủ công mà cần thuật toán để cài đặt vào máy tính và nhờ máy tính làm giúp.

Ví dụ, dãy gồm 8 số: 2, 3, 1, 3, 5, 2, 2, 8 thì dãy có 5 giá trị khác nhau và số lần lặp của giá trị xuất hiện nhiều nhất trong dãy là 3.

Yêu cầu: Cho một dãy A gồm N số tự nhiên. Gọi Q là số lượng giá trị khác nhau có trong dãy và P là số lần lặp của giá trị xuất hiện nhiều nhất trong dãy A. Hãy tìm Q và P.

Dữ liệu vào: Từ tệp văn bản COUNT.INP gồm:

• Dòng 1: chứa số nguyên N (1 ≤ N ≤ 10⁷);
• Dòng 2: chứa N số tự nhiên A₁, A₂, …, A_N (0 ≤ Aᵢ ≤ 10⁷; ∀i = 1..N và các số cách nhau ít nhất một dấu cách).

Kết quả: Ghi ra tệp văn bản COUNT.OUT gồm:

• Dòng 1: ghi số Q;
• Dòng 2: ghi số P.

Ví dụ:

COUNT.INP	COUNT.OUT
8 2 3 1 3 5 2 2 8	5 3

Ràng buộc:

• Có 70% test tương ứng 70% số điểm với N và Aᵢ ≤ 10⁴;
• Có 30% test còn lại tương ứng 30% số điểm với N và Aᵢ ≤ 10⁷.

Bài 4. Siêu thị

Trong siêu thị có n gói hàng. Với mỗi i (1 ≤ i ≤ n), gói hàng thứ i có trọng lượng là Wᵢ (1 ≤ Wᵢ ≤ 100) và giá trị Vᵢ (1 ≤ Vᵢ ≤ 100). Chị Hoa vào siêu thị để mua sắm đồ dùng gia đình nhưng sức của chị không thể mang được trọng lượng gói hàng vượt quá M (1 ≤ M ≤ 100). Hỏi chị Hoa sẽ mua được những gói hàng nào để được tổng giá trị lớn nhất.

Yêu cầu: Em hãy giúp chị Hoa tìm tổng giá trị lớn nhất của các gói hàng được chọn để mang đi.

Dữ liệu vào: Từ tệp văn bản MARKET.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương n và M;
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương Wᵢ và Vᵢ (các số cách nhau ít nhất một dấu cách).

Kết quả: Ghi ra tệp văn bản MARKET.OUT gồm một số duy nhất cần tìm. Trường hợp không chọn được gói hàng nào thì ghi kết quả là −1.

Ví dụ:

MARKET.INP	MARKET.OUT
3 8 3 30 4 50 5 60	90

Giải thích: Gói hàng thứ 1 và thứ 3 sẽ được chọn để mang đi. Vì chúng có tổng khối lượng không quá 8 và có giá trị lớn nhất là 90.

Ràng buộc:

• Có 80% test tương ứng 80% số điểm với n ≤ 30;
• Có 20% test còn lại tương ứng 20% số điểm với n ≤ 100.