Kỳ thi học sinh giỏi cấp tỉnh THCS môn Tin học - Năm học 2021-2022 - Sở GD&ĐT Quảng Nam (Có hướng dẫn chấm)

SỞ GIÁO DỤC VÀ ĐÀO TẠO

TỈNH QUẢNG NAM

(Đề gồm có 03 trang)

KỲ THI HỌC SINH GIỎI CẤP TỈNH THCS

NĂM HỌC 2021 - 2022 Môn thi: TIN HỌC Thời gian: 150 phút (không kể thời gian giao đề) Ngày thi: 19/4/2022

Tổng quan đề thi

Tên bài Tên file chương trình Dữ liệu vào Dữ liệu ra

Bài 1: Tổng và lũy thừa SPOW.* SPOW.INP SPOW.OUT

Bài 2: Xâu đối xứng PALIN.* PALIN.INP PALIN.OUT

Bài 3: Đếm giá trị COUNT.* COUNT.INP COUNT.OUT

Bài 4: Siêu thị MARKET.* MARKET.INP MARKET.OUT

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Free Pascal hoặc C++.

Bài 1. (5.0 điểm) Tổng và lũy thừa

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

Yêu cầu: Gọi S là tổng của a và n, T là lũy thừa an. 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).

Dữ liệu ra: 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 109+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 ≤ 106;

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

Bài 2. (5.0 điểm) 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.

ĐỀ CHÍNH THỨC

DeThi.edu.vn

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 ≤ 104) là số lượng xâu S;

 T dòng tiếp theo, mỗi dòng chứa một xâu S.

Dữ liệu ra: 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. (5.0 điểm) Đế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 107. 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 107 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 ≤ 107);

 Dòng 2: chứa N số tự nhiên A1, A2,..., AN (0 ≤ Ai ≤ 107; và các số cách nhau ít

nhất một dấu cách).

Dữ liệu ra: Ghi ra tệp văn bản COUNT.OUT gồm:

 Dòng 1: ghi số Q;

 Dòng 2: ghi số P.

1, i N 

DeThi.edu.vn