Giải đề thi HSG tỉnh nghệ an 2011-2012

ĐỀ HỌC SINH GIỎI TỈNH NGHỆ AN NĂM 2011-2012
MÔN TIN HỌC

(Chú ý: Mọi chương trình dưới đây đều được tách ra từng modun nhằm chúng ta hiểu thuật toán, nên không có sự tối ưu về thuật toán để giảm thời gian hay dư thừa dữ liệu.
Quý vị cũng có thể có nhiều cách giải hay hơn).

Bài 1: Nén xâu
Một xâu kí tự có thể nén lại thành 1 một xâu mới bằng cách nén các kí tự giống nhau đứng cạnh nhau. Ví dụ trong xâu AAAA sẽ nén thành 4A. Hãy lập trình để nén 1 xâu kí tự in hoa theo cách trên.
Dữ liệu: vào từ file văn bản NENXAU.INP một xâu, mà các kí tự là chữ cái in hoa.
Kết quả: ghi vào file văn bản NENXAN.OUT một xâu kí tự sau khi nén.
VD:
Nenxau.inp
Nenxau.out

NNNAAAAFGGH
3N4AF2GH

Ở bài này thì có nhiều cách giải.
Mình đưa ra một cách giải như sau:
- Nhóm các phần tử giống nhau lại và tính chiều dài của xâu đó.
- Nhóm cuối cùng có thể có số phần tử “bằng” hoặc “không bằng” 1. Nên phải xử lý riêng
Thuật toán: Xâu cần nén là xâu ST
- Đầu tiên tạo 1 xâu có 1 phần tử (S) (chính là ký tự đầu tiên của xâu cần nén (St)) S:=St[1];
- Duyệt từ phần tử thứ 2 đến phần tử cuối cùng: for i:=2 to length(st) do
+ Gặt phần tử đang xét St[i] bàng S[1] thì cộng vào xâu S luôn.
+ Nếu St[i] <> S[1] ( Đã hết đoạn các ký tự trùng nhau (Xâu S bây giờ gồm các phần tử giống nhau) ( Lưu lại độ dài xâu S vào tệp + 1 ký tự trong xâu S; Tiến hành khởi tại lại xâu S:=St[i] (Bắt đầu đoạn mới)
for i:=2 to length(st) do
if St[i]=S[1] then S:=S+St[i]
else
Begin
if length(s)>1 then write(f,length(s));
write(f,S[1]);
S:=St[i];
End;
- Còn vị trí = length(St) ta chưa lưu lại được
+ sau vòng for trên kia thì xâu S có 2 trường hợp
- Chỉ một ký tự cuối cùng của xâu St
- Đoạn cuối cùng của xâu St (nếu có nhiều PT giống nhau)
if length(s)=1 then write(f,S)
else write(f,length(s),S[1]);
Chương trình hoàn chỉnh
Program NenXau;
Var St:string;
Procedure Docfile;
var f:text;
Begin
assign(f,`nenxau.inp`); reset(f);
readln(f,st);
close(f);
End;
Procedure XuLy;
var f:text;
s:string;
i:byte;
Begin
assign(f,`nenxau.Out`);
rewrite(f);
s:=st[1];
for i:=2 to length(st) do
if St[i]=S[1] then S:=S+St[i]
else
Begin
if length(s)>1 then write(f,length(s));
write(f,S[1]);
S:=St[i];
End;
if length(s)=1 then write(f,S)
else write(f,length(s),S[1]);
close(f);
End;
Begin
docfile;
XuLy;
End.

Bài 2: Số nguyên tố đối xứng
Một số nguyên dương T được gọi là số nguyên tố đối xứng nếu thỏa mãn các yêu cầu sau:
T là một số nguyên tố
T là một số đối xứng (đọc T từ trái qua phải thu được kết quả giống như đọc T từ phải qua trái). Ví dụ 12321 là 1 số đối xứng.
Yêu cầu: cho 2 số nguyên dương A và B, hãy tìm số lượng các số nguyên tố đối xứng T thỏa mãn A ≤ T ≤ B 100000
Dữ liệu: vào từ file văn bản NTDX.INP gồm 1 dòng chứa 2 số nguyên dương A và B cách nhau 1 dấu cách (104 ≤