Đề thi HSG Quảng Ngãi Năm 2005 (đề 2)

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN HSG TỈNH - THPT
QUẢNG NGÃI Năm học 2004-2005


Tên bài
Tên chương trình
Dữ liệu vào
Kết quả

BÀI 1
Phân lớp
CLASS.PAS`
CLASS.IN
CLASS.OU

BÀI 2
Palindrome
PALINDR.PAS
PALINDR.IN
PALINDR.OU


Bài 1: Phân lớp (10 điểm) Tên chương trình: CLASS.PAS
Gọi S(x) là số ước của số nguyên dương x. Hai số nguyên dương x và y được gọi là hai số cùng lớp k nếu S(x) = S(y) = k .
Ví dụ: S(6) = 4 vì 6 có bốn ước là 1, 2, 3, và 6.
S(8) = 4
S(7) = 2
S(13) = 2
Như vậy, 6 và 8 là hai số thuộc lớp 4 , 7 và 13 là hai số thuộc lớp 2.
Cho N số nguyên dương a1, a2, ..., aN. Hãy cho biết:
Các số đã cho được chia thành bao nhiêu lớp khác nhau.
Số lượng phần tử trong mỗi lớp là bao nhiêu?
Dữ liệu vào: Vào từ tập tin văn bản CLASS.IN:
Dòng đầu tiên ghi số nguyên N, 1 ≤ N ≤ 1000
Tiếp đến là N số nguyên dương a1, a2, ... ,aN, có thể viết trên nhiều dòng, mỗi số được viết cách nhau ít nhất một dấu cách, 1 ≤ ai ≤ 65530
Kết quả: Đưa ra tập tin văn bản:
Dòng đầu tiên là số lớp S tìm được.
Tiếp đến là S dòng, mỗi dòng chứa hai giá trị k và d , trong đó k là số ước của các số trong lớp, d là số phần tử có trong lớp k. Mỗi số được cách nhau ít nhất bởi một dấu cách.
class.in
class.ou

5
6 2 13
7 8
2
2 3
4 2

Bài 2: Palindrome (10 điểm) Tên chương trình: PALINDR.PAS
Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome.
Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:
‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’
‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’
‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’
Yêu cầu: Cho xâu ký tự s, cần tìm cách biểu diễn xâu s dưới dạng một dãy gồm số ít nhất các palindrome.
Ví dụ: Cho s=‘bobseesanna’, do ta có ‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’ và không thể biểu diễn ‘bobseesanna’ bởi ít hơn là 3 palindrome nên biểu diễn này chính là biểu diễn cần tìm.
Dữ liệu vào: Vào từ tập tin văn bản PALINDR.IN, gồm một dòng chứa xâu ký tự s gồm không quá 255 ký tự.
Kết quả: Đưa ra tập tin văn bản PALINDR.OU:
Dòng đầu tiên ghi k là số lượng ít nhất các palindrome trong biểu diễn tìm được;
Dòng thứ i trong số k dòng tiếp theo ghi palindrome pi (i=1, 2, ..., k) sao cho s = p1p2...pk.
PALINDR.IN
PALINDR.OU

PALINDR.IN
PALINDR.OU

bobseesanna
3
bob
sees
anna

aabbaaaabb
2
aa
bbaaaabb


Bài 1
uses crt;
const
fn = `class.in`; gn = `class.ou`; hn = `class.ts`;
mn = 1000; bl = #32; sotest = 5;

type ww = word;
mw1 = array[0..mn+1] of ww;

var
f,g: text;
n,solop,solophs:ww;
ch: char;
a,u,d,spt,su: mw1;
soloi: ww;
diemtest: array[1..sotest] of ww;
tongdiem: ww;
spths,souochs:ww;

procedure xem(var x: mw1);
var i:ww;
begin
writeln; writeln(n);
for i:=1 to n do write(x[i],bl);
end;

function souoc(x