tTrong số báo tháng 5 trước có đăng đề thi "Olympic tin học sinh viên lần thứ XII, 2003". Tôi xin mạo muội trao đổi cùng bạn đọc về đề thi trên.
Nhận xét chung: Cả ba bài trong đề thi đều khá hay, phù hợp với khối không chuyên, và đều có giải thuật tối ưu. Sau đây tôi xin đề cập về từng bài. ở đây tôi không nhắc lại đề bài các bạn có thể xem lại số báo trước.
Bài 1: SARS Trong ba bài, thì bài này có lẽ "dễ chịu" hơn cả. Đề bài khá rõ để dẫn đến giải thuật. Và việc áp dụng thuật toán tìm vùng liên thông trong đồ thị vô hướng khá dễ dàng. Thiết nghĩ phần cài đặt chương trình bạn đọc có thể làm được. Tôi xin qua bài tiếp theo.
Bài 2: Tách từ Bài này khá hay, nếu để ý bạn có thể thấy rằng bài toán có thể đưa về bài toán quy hoạch động. Nếu đã nhận thấy đây là bài toán quy hoạch động thì việc quy hoạch động như thế nào không mấy khó khăn. Cái chính vẫn là làm sao nhận dạng được mô hình bài toán!. Và điều quan trọng nữa là việc tổ chức dữ liệu phù hợp với hướng giải trên.
ở đây tôi sử dụng mảng hai chiều Fij để đánh dấu. Ta xét tất cả các cách tạo nên chuỗi con của S từ chuỗi con của S1 và chuỗi con của S2 (Chuỗi con chỉ xét ở đây là chuỗi con có phần tử đầu tiên của chuỗi mẹ. Ví dụ: "abc" thì các chuỗi con là "a", "ab" hay "abc" còn "bc" không xét đến). F[i,j] được đánh dấu nếu ta đã xác định cách tạo nên chuỗi con của S có độ dài i+j từ chuỗi con của S1 có độ dài i và chuỗi con của S2 có độ dài j.
F[i,j] = 1 nếu S1[i] = S[i+j] F[i,j] = 2 nếu S2[j] = S[i+j]
Và rõ ràng việc đánh dấu F[i,j] phải dựa vào F[i-1,j] hoặc F[i,j-1] có được đánh dấu hay không. Đoạn chương trình quy hoạch động chính như sau:
for i:=1 to length(S1) do for j:=1 to length(S2) do begin   if (F[i-1,j]>0) and (S1[i]=S[i+j]) then F[i,j]:=1;   if (F[i,j-1]>0) and (S2[j]=S[i+j]) then F[i,j]:=2; end;
Từ Fij được đánh dấu như trên thì việc tìm ngược lại kết quả cũng trở nên dễ dàng.
Chương trình: Program Tach_tu;
Program Tach_tu;
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 65520,0,655360}
Const
inp=`TachTu.Inp`;
out=`TachTu.Out`;
Var
F:array[0..100,0..100] of byte;
S1,S2,S:string;
l1,l2:byte;
fo:text;

Procedure Input;
var
fi:text;
begin
assign(fi,inp);
reset(fi);
readln(fi,S1);
readln(fi,S2);
readln(fi,S);
close(fi);
end;

Procedure Solve;
var
i,j:byte;
begin
l1:=length(S1);
l2:=length(S2);
fillchar(F,sizeof(F),0);
for i:=1 to l1 do F[i,0]:=1;
for j:=1 to l2 do F[0,j]:=2;
for i:=1 to l1 do
for j:=1 to l2 do
begin
if (F[i-1,j]>0) and (S1[i]=S[i+j]) then F[i,j]:=1;
if (F[i,j-1]>0) and (S2[j]=S[i+j]) then F[i,j]:=2;
end;
end;

Procedure PrintResult(i,j:byte);
begin
if F[i,j]>0 then
begin
case F[i,j] of
1: PrintResult(i-1