onthicaptoc.com
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT
TỈNH QUẢNG NAM NĂM HỌC 2021 - 2022 Môn thi : TIN HỌC 12
ĐỀ CHÍNH THỨC Thời gian : 150 phút (không kể thời gian giao đề)
Ngày thi : 22/03/2022
(Đề thi có 03 trang)

TỔNG QUAN ĐỀ THI TỔNG QUAN ĐỀ BÀI
Bài
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Thời gian
1
Tổng chữ số
TOTAL.*
TOTAL.INP
TOTAL.OUT
1 s
2
Chênh lệch nhỏ nhất
DIFF.*
DIFF.INP
DIFF.OUT
1 s
3
Tổng bằng 0
ZSEQ.*
ZSEQ.INP
ZSEQ.OUT
1 s
4
Đếm dãy số
CNTSEQ.*
CNTSEQ.INP
CNTSEQ.OUT
1 s

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à Pascal hoặc C++.
Hãy lập trình giải các bài toán sau:
Bài 1. (5 điểm) Tổng chữ số
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’). Hãy tính tổng các chữ số có mặt trong xâu đó. Ví dụ: xâu S:=‘a20B2C2’ kết quả là 6.
Yêu cầu: Gọi T là tổng các chữ số có mặt trong xâu đó. Hãy viết chương trình tìm giá trị T.
Dữ liệu vào: Từ tệp văn bản TOTAL.INP gồm một xâu S.
Kết quả: Ghi ra tệp văn bản TOTAL.OUT gồm một số nguyên là số T tìm được.
Ví dụ:
TOTAL.INP
TOTAL.OUT
123
6
TOTAL.INP
TOTAL.OUT
a20B2C2
6
Ràng buộc:
* Có 50% test tương ứng 50% số điểm với xâu S độ dài không quá 255 và chỉ chứa chữ số (‘0’..’9’);
* Có 50% test tương ứng 50% số điểm còn lại với xâu S độ dài không quá 106.
Bài 2. (5 điểm) Chênh lệch nhỏ nhất
Cho hai số nguyên dương L và R (1 ≤ L < R ≤ 109).
Yêu cầu: Tìm số nguyên dương M (L ≤ M < R) để chênh lệch giữa tổng các số nguyên liên tiếp từ L đến M và tổng các số nguyên liên tiếp từ M+1 đến R là nhỏ nhất.
Dữ liệu vào: Từ tệp văn bản DIFF.INP gồm hai số nguyên dương L và R.
Kết quả: Ghi vào tệp văn bản DIFF.OUT một số nguyên duy nhất là số M thỏa mãn đề bài.
Ví dụ:
DIFF.INP
DIFF.OUT
Giải thích
2 7
5
Tổng từ 2 đến 5 là: 14
Tổng từ 6 đến 7 là: 13
Chênh lệch là: 1
Ràng buộc:
* Có 60% test tương ứng 60% số điểm của bài với L < R ≤ 103;
* Có 20% test tương ứng 20% số điểm của bài với L < R ≤ 106;
* Có 20% test tương ứng 20% số điểm còn lại của bài với L < R ≤ 109.
Bài 3. (5 điểm) Tổng bằng 0
Cho dãy số nguyên gồm N phần tử a1, a2, …, aN. Gọi Q là số lượng dãy con liên tiếp có tổng bằng 0.
Yêu cầu: Hãy viết chương trình tìm Q.
Ví dụ: N=5 với dãy: 2, 1, -2, 3, -2 thì Q=1, dãy con đó là 1,-2, 3, -2.
Dữ liệu vào: Từ tệp văn bản ZSEQ.INP có cấu trúc:
− Dòng đầu tiên chứa số tự nhiên N(1 ≤ N ≤ 105);
− Dòng tiếp theo chứa dãy số nguyên gồm N phần tử a1, a2, …, aN. (|ai| ≤ 109), các số cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản ZSEQ.OUT gồm một số Q duy nhất.
Ví dụ:
ZSEQ.INP
ZSEQ.OUT
5
2 1 -2 3 -2
1
Ràng buộc:
* Có 60% test tương ứng 60% số điểm của bài với N ≤ 102;
* Có 20% test tương ứng 20% số điểm của bài với N ≤ 104;
* Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 105.
Bài 4. (5 điểm) Đếm dãy số
Cho số nguyên dương n (n ≤ 1018 ). Hãy đếm số dãy số nguyên X = (x1, x2,…, xn) gồm n phần tử thỏa mãn:
− Tổng các phần tử của X chia hết cho 3;
− 0 ≤ xi ≤ 2 với mọi i thuộc tập hợp {1, 2, …, n}.
Dữ liệu vào: Từ tệp văn bản CNTSEQ.INP gồm một dòng duy nhất chứa số nguyên n. Kết quả: Ghi ra tệp văn bản CNTSEQ.OUT gồm một số duy nhất là kết quả của bài toán sau khi chia lấy dư cho 109+7.
Ví dụ:
CNTSEQ.INP
CNTSEQ.OUT
2
3
Giải thích
Với n = 2 ta có các dãy X sau:
− X = (1, 2);
− X = (0, 0); − X = (2, 1).
Ràng buộc:
* Có 60% test tương ứng 60% số điểm của bài với n ≤ 10;
* Có 20% test tương ứng 20% số điểm của bài với n ≤ 103; • Có 20% test tương ứng 20% số điểm còn lại của bài với n ≤ 1018.

---------------HẾT---------------



(Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm)
Họ và tên thí sinh: .............................................................. Số báo danh: ...............................
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT
TỈNH QUẢNG NAM NĂM HỌC: 2021 - 2022
HDC CHÍNH THỨC
Môn thi : TIN HỌC 12


HƯỚNG DẪN CHẤM
Bài thi chấm bằng test và chấm bằng phần mềm Themis kèm theo (phần mềm mới nhất của thầy Lê Minh Hoàng và Đỗ Đức Đông)

Bài 1. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, thời gian chạy 1s/1test, bộ nhớ
1024 MB
 Sub1: Có 50% test tương ứng 50% số điểm với xâu S độ dài không quá 255 và chỉ chứa chữ số (‘0’..’9’);
 Sub2: Có 50% test tương ứng 50% số điểm còn lại với xâu S độ dài không quá 106.

TEST
TOTAL.INP
TOTAL.OUT
1
662744111
32
2
a20B2C2
6
…
...
...
20
...
...

Bài 2. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, thời gian chạy 1s/1test, bộ nhớ 1024 MB
 Sub1: Có 60% test tương ứng 60% số điểm của bài với L < R ≤ 103;
 Sub2: Có 20% test tương ứng 20% số điểm của bài với L < R ≤ 106;
 Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với L < R ≤ 109.

TEST
DIFF.INP
DIFF.OUT
1
6 864
611
2
134 184
161
…
...
...
20
...
...

Bài 3. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, thời gian chạy 1s/1test, bộ nhớ 1024 MB
 Sub1: Có 60% test tương ứng 60% số điểm của bài với N ≤ 102;
 Sub2: Có 20% test tương ứng 20% số điểm của bài với N ≤ 104;
 Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 105.

TEST
ZSEQ.INP
ZSEQ.OUT
1
5
2 1 -2 3 -2
1
2
8
3 -5 2 6 2 -1 5 -5
2
…
...
...
20
...
...

Bài 4. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, thời gian chạy 1s/1test, bộ nhớ 1024 MB
 Sub1: Có 60% test tương ứng 60% số điểm của bài với n ≤ 10;
 Sub2: Có 20% test tương ứng 20% số điểm của bài với n ≤ 103;
 Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với n ≤ 1018.

TEST
CNTSEQ.INP
CNTSEQ.OUT
1
2
3
2
6
243
…
...
...
20
...
...



---------------HẾT ---------------
onthicaptoc.com

onthicaptoc.com De thi HSG Tin 12 Quang Nam 2022