Đề thi chọn HSG

SỞ GD&ĐT NGHỆ AN



(Đề thi có 02 trang)
KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11 CẤP THPT
NĂM HỌC 2016 - 2017

Môn thi: TIN HỌC - BẢNG A
Thời gian: 150 phút (không kể thời gian giao đề)



Tổng quan bài thi:

Tên bài
File nguồn
File Input
File Output
Thời gian chạy

PERFECT
PERFECT.*
PERFECT.INP
PERFECT.OUT
1 giây

PALIN
PALIN.*
PALIN.INP
PALIN.OUT
1 giây

SEQ
SEQ.*
SEQ.INP
SEQ.OUT
1 giây

GN
GN.*
GN.INP
GN.OUT
1 giây


Chú ý: 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à ngôn ngữ lập trình PASCAL hoặc ngôn ngữ lập trình C++

Hãy lập trình giải các bài toán sau:

Bài 1 (6.0 điểm): PERFECT
Trong một buổi học toán, Bông được học khái niệm về số có tính chất đặc biệt: Đó là số hoàn hảo. Số A được gọi là số hoàn hảo nếu:
A = B1 + B2 + … + Bk trong đó Bi là ước của A và Bi < A với
.
Ví dụ: Số 6 là số hoàn hảo vì nó có tổng các ước 1 + 2 + 3 = 6, số 8 không phải là số hoàn hảo vì 1 + 2 + 4 = 7, (7≠ 8).
Yêu cầu: Cho dãy số a1, a2, ..., an. Hãy giúp Bông đếm xem trong dãy có bao nhiêu số có tổng các chữ số là số hoàn hảo.
Dữ liệu vào: Từ file văn bản PERFECT.INP gồm:
- Dòng đầu tiên là số nguyên dương n (n ≤ 100).
- Dòng thứ 2 ghi n số nguyên a1, a2, ..., an (0 ≤ ai ≤ 109).
Kết quả: Ghi ra file văn bản PERFECT.OUT gồm: Một số duy nhất là kết quả của bài toán.
Ví dụ:
PERFECT.INP
PERFECT.OUT

3
6 123 28
2


Bài 2 (6.0 điểm): PALIN
Một xâu S được gọi là xâu đối xứng nếu S = S` với S` là xâu nhận được từ xâu S khi đọc từ phải qua trái.
Ví dụ: Xâu `aba` là xâu đối xứng, còn xâu `abc` là xâu không đối xứng.
Cho một xâu S gồm n kí tự (1 ≤ n ≤ 100)
Yêu cầu: Hãy tìm cách chia xâu S thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.
Dữ liệu vào: Từ file văn bản PALIN.INP gồm:
- Dòng đầu gồm một số nguyên n là độ dài của xâu S.
- Dòng thứ hai là nội dung xâu S.
Kết quả: Ghi ra file văn bản PALIN.OUT gồm:
- Dòng đầu ghi một số nguyên k (số đoạn ít nhất tìm được).
- K dòng sau, mỗi dòng ghi một số nguyên ti, với ti là vị trí kết thúc của đoạn thứ i.
Ví dụ:
PALIN.INP
PALIN.OUT

 8
abbacdcb

3
4
7
8


Bài 3 (4.0 điểm): SEQ
Cho dãy số gồm n số nguyên a1, a2, …, an và 2 số nguyên không âm L, R (L ≤ R).
Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai+…+aj| ≤ R .
Dữ liệu vào: Từ file văn bản SEQ.INP gồm:
- Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109)
- Dòng thứ hai chứa n số nguyên dương a1, a2,…, an (ai ≤ 109)
Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được.
Ví dụ:
SEQ.INP
SEQ.OUT

3 0 1
1 -1 2
4

Hạn chế: - Có 50% số test ứng với 0 < n ≤ 103
- Có 50% số test ứng với 103 < n ≤ 105

Bài 4 (4.0 điểm): GN
Người ta đo độ giống nhau của hai xâu X, Y có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số i thỏa mãn X[i] = Y[i].
Ví dụ: X = `avbc`; Y = `avvv` có độ giống nhau bằng 2.