HSG lớp 9 Lào Cai 2022-2023

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH LÀO CAI Năm học 2022 - 2023

MÔN TIN HỌC 5 bài: bai1 - bai5

Bài 1. Độ đẹp

Một số tự nhiên N có càng nhiều ước số tự nhiên thì càng đẹp, em hãy tính độ đẹp của một số tự nhiên N bất kì.

Dữ liệu vào: Đọc từ tệp bai1.inp ghi duy nhất một số tự nhiên N, biết N ≤ 10¹⁴.

Kết quả: Ghi ra tệp bai1.out một số duy nhất là số ước của N.

Ví dụ:

bai1.inp	bai1.out	Giải thích
`4`	`3`	Số 4 có 3 ước là: 1, 2, 4
`1234`	`4`	Số 1234 có các ước là: 1, 2, 617, 1234

Có 85% test chấm bài có 1 ≤ N < 10⁸;
Có 15% test chấm bài có 10⁹ ≤ N ≤ 10¹⁴.

Bài 2

Một số tự nhiên gọi là đối xứng khi viết các chữ số của nó theo chiều ngược lại thì ta vẫn thu được chính nó. Ví dụ như các số 66, 121 là số đối xứng.

Một số được coi là số đẹp nếu nó là số đối xứng và có từ 3 ước số nguyên tố khác nhau trở lên. Ví dụ: số 282 là số đẹp vì nó đối xứng và có 3 ước là số nguyên tố khác nhau là: 2, 3, 47. Hoặc số 858 cũng là số đẹp vì nó đối xứng và có 4 ước nguyên tố khác nhau là: 2, 3, 11, 13.

Yêu cầu: Cho hai số nguyên dương a, b. Đưa ra số lượng số đẹp trong đoạn từ a đến b.

Dữ liệu vào: Đọc vào từ tệp bai2.inp là hai số nguyên dương a, b (1 < a < b ≤ 10⁷).

Kết quả: Ghi kết quả ra tệp bai2.out là số lượng số đẹp trong đoạn a đến b.

Ví dụ:

bai2.inp	bai2.out	Giải thích
`1 1000`	`25`	Số đẹp trong đoạn 1 đến 1000: 66, 222, 252, 282, 414, 434, 444, 474, 494, 525, 555, 585, 595, 606, 616, 636, 646, 666, 696, 777, 828, 858, 868, 888, 969.

Có 80% số test chấm có: 1 ≤ N ≤ 10⁴.
Có 20% số test chấm có: 10⁵ < N ≤ 10⁷.

(N ở đây được hiểu là giá trị b.)

Bài 3

Cho dãy số tự nhiên gồm N phần tử: a₁, a₂, …, a_N và một số tự nhiên K.

Yêu cầu: Đếm số lượng cặp chỉ số (i, j) mà i < j và aᵢ + aⱼ = K trong dãy.

Dữ liệu vào: Đọc dữ liệu vào từ tệp bai3.inp:

Dòng đầu là hai số nguyên dương N, K (2 ≤ N ≤ 3×10⁶; 1 ≤ K ≤ 10⁶).
Dòng sau là dãy số: a₁, a₂, …, a_N các số đều không quá 10⁶.

Kết quả: Ghi kết quả ra tệp bai3.out là số lượng cặp aᵢ, aⱼ có tổng bằng K.

Ví dụ:

bai3.inp	bai3.out	Giải thích
`5 1` `1 5 4 1 2`	`0`	Không có cặp aᵢ + aⱼ = 1
`4 6` `3 2 3 3`	`3`	Có 3 cặp (a₁, a₃); (a₁, a₄); (a₃, a₄) có tổng bằng 6

Có 80% số test chấm có: 1 ≤ N ≤ 10³.
Có 20% số test chấm có: 10³ < N ≤ 3×10⁶.

Bài 4

Cho một xâu kí tự X gồm các chữ cái in thường từ ‘a’ đến ‘z’. Độ dài của xâu X không quá 10⁶. Người ta mã hóa xâu X thành xâu Y theo cách như sau:

Ban đầu xâu Y rỗng.

Đưa một kí tự trong xâu X vào cuối của xâu Y và lập tức đảo ngược xâu Y. Các kí tự của xâu X cứ đưa lần lượt như thế vào xâu Y.

Em hãy in ra xâu Y cuối cùng nhận được khi đã đưa hết các kí tự của xâu X vào.

Dữ liệu vào: Đọc vào từ tệp bai4.inp ghi một dòng duy nhất là xâu X.

Kết quả: Ghi ra tệp bai4.out ghi một dòng duy nhất là xâu Y.

Ví dụ:

bai4.inp	bai4.out	Giải thích
`abc`	`cab`	Đưa lần lượt các kí tự vào ta được xâu Y như sau: Bước 1: Thêm ‘a’ và đảo ngược ta được Y = a Bước 2: Thêm ‘b’ và đảo ngược ta được Y = ba Bước 3: Thêm ‘c’ và đảo ngược ta được Y = cab

Có 55% test chấm bài có độ dài xâu X không quá 255;
Có 20% test chấm bài có độ dài xâu X không quá 10⁴;
Có 25% test chấm bài có độ dài xâu X không quá 10⁶.

Bài 5

Cho dãy gồm N số tự nhiên: a₁, a₂, …, a_N. Người ta gọi một đoạn gồm các phần tử liên tiếp bất kì trong dãy ban đầu là đoạn con. Hai đoạn con là khác nhau nếu tồn tại ít nhất một phần tử không thuộc vào cả hai đoạn. Ví dụ dãy (a₁; a₂; a₃; a₄) thì có mười đoạn con là: (a₁), (a₂), (a₃), (a₄), (a₁; a₂), (a₂; a₃), (a₃; a₄), (a₁; a₂; a₃), (a₂; a₃; a₄), (a₁; a₂; a₃; a₄).

Hãy đếm số đoạn con mà có tổng các lũy thừa bậc M của các phần tử của đoạn đó chia hết cho K.

Dữ liệu vào: Đọc dữ liệu vào từ tệp bai5.inp:

Dòng đầu ghi 3 số tự nhiên N, M, K tương ứng là số phần tử của dãy ban đầu, số mũ, và số K cần chia hết (1 ≤ N ≤ 10⁵; 1 ≤ M ≤ 10¹⁸; 1 ≤ K ≤ 10⁵).
Dòng tiếp theo ghi N số tự nhiên a₁, a₂, …, a_N (các số đều không vượt quá 10⁵⁰, hay là: 0 ≤ aᵢ ≤ 10⁵⁰ với mọi i).

Kết quả: Ghi kết quả ra tệp bai5.out: số đoạn con mà có tổng các lũy thừa bậc M của các phần tử chia hết cho K.

Ví dụ:

bai5.inp	bai5.out	Giải thích
`4 1 3` `3 2 1 5`	`4`	Có các đoạn (3), (2; 1), (1; 5), (3; 2; 1) vì: 3¹ ⋮ 3; (2¹ + 1¹) ⋮ 3; (1¹ + 5¹) ⋮ 3; (3¹ + 2¹ + 1¹) ⋮ 3
`4 2 3` `3 2 1 5`	`3`	Có các đoạn (3), (2; 1; 5), (3; 2; 1; 5) vì: 3² ⋮ 3; (2² + 1² + 5²) ⋮ 3; (3² + 2² + 1² + 5²) ⋮ 3

Có 45% test chấm bài có M = 1, N ≤ 10³, aᵢ ≤ 10⁶;
Có 30% test chấm bài có M ≤ 1000, N ≤ 10⁵, aᵢ ≤ 10⁹;
Có 25% test chấm bài có 10⁹ ≤ M ≤ 10¹⁸, N ≤ 10⁵, 10³⁰ ≤ aᵢ ≤ 10⁵⁰.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English