Đáp án HSG tin học ĐBSCL

SỞ GD&ĐT BẠC LIÊU KỲ THI HSG ĐBSCL LẦN THỨ 16 - NĂM 2009

Đề thi đề nghị Môn: Tin học
(Gồm 3 câu) Thời gian: 180 phút (Không kể thời gian giao đề)

HƯỚNG DẪN CHẤM:

Câu 1 (6 điểm) - Cặp số song sinh
Ta đặt c= a xor b hoặc đặt c= |a-b| cũng được (mặc dù kết quả ra không giống nhau, nhưng tính chất cần xét thì giống nhau)
Xét c: Nếu c = 2k thì a, b chính là cặp số song sinh. Ngược lại thì không.
Cách tạo test:
Cho 2 số a và b bằng nhau.
Cộng vào a hoặc b 1 số dạng 2k (rất dễ tính nhẫm) ta được cặp số song sinh.
Cộng vào a hoặc b 1 số dạng <> 2k ta được 2 số không phải là cặp số song sinh.
Cách chấm:
Vì trong lúc tạo bộ input ta đã nhẫm tính được kết quả nên việc chấm chỉ còn là so sánh kết quả.
Câu 2 (7 điểm) - Điền khuyết xâu kí tự
Ta xóa bớt trong a và b 1 vài ký tự để thu được xâu kí tự con giống nhau dài nhất. Sau đó ta điền khuyết những ký tự dư ra bên a vào bên b và ngược lại.
Bài này rất khó tạo ra những test khó. Ngoại trừ ta cho 2 xâu bất kỳ rồi viết chương trình kiểm tra lại thì được. Còn việc nhẫm tính thì chỉ tạo ra được các test đơn giản thôi.
Chương trình kiểm tra gợi ý: cho trước 2 xâu rồi sinh ra kết quả

Var a:array[0..100,0..100] of byte;
s1,s2,s3,s4:string;
i,j:byte;
Begin
s1:=`121212qqw12121212`;
s2:=`121wer21212121212`;
s3:=``;
For i:=0 to length(s1) do
a[0,i]:=0;
For i:=1 to length(s2) do
a[i,0]:=0;
For i:=1 to length(s1) do
For j:=1 to length(s2) do
Begin
If s1[i]=s2[j] then a[i,j]:= a[i-1,j-1]+1 else
If a[i-1,j]>a[i,j-1] then a[i,j]:= a[i-1,j]
Else a[i,j]:= a[i,j-1];
End;
i:= length(s1);
j:= length(s2);
Repeat
Begin
If (s1[i] = s2[j]) and (a[i,j] = a[i-1,j-1]+ 1) then
Begin
s3:=s1[i]+s3;
dec(j); dec(i);
End else
If a[i,j] = a[i-1,j] then dec(i) else dec(j);
End;
Until (i*j=0);
s4:=``;
For i:=1 to length(s3) do
Begin
s4:=s4+ copy(s1,1,pos(s3[i],s1)-1);
delete(s1,1,pos(s3[i],s1));
s4:=s4+ copy(s2,1,pos(s3[i],s2)-1);
delete(s2,1,pos(s3[i],s2));
s4:=s4+s3[i];
End;
s4:=s4+s1+s2;
Write(s4);
Readln;
end.


Chú ý khi chấm bài vì bài này cho ra những xâu kết quả khác nhau, nên ta xét chiều dài xâu sinh ra và tính nhẫm 1 hoặc 2 trường hợp khác đáp án là được.
Câu 3 (7 điểm) - Dãy đặc biệt
Để giải được bài này thì học sinh cần phải nắm được kỹ thuật tạo ma phương chẵn, ma phương lẻ, vào một số phép toán biến đổi số học.

Cách tạo test.
Để tạo dãy không thỏa mãn thì có các cách sau:
N không là số chính phương hoặc có sự trùng lặp giữa các phần tử trong dãy.
N là số chính phương. Tổng các phần tử trong dãy không chia hết cho căn bậc 2 của n.
Còn một số trường hợp đặc biệt khác chúng ta không cần quan tâm.
Để tạo ra dãy là dãy đặc biệt thì:
N là số