Một số bài toán luyện đội tuyển Tin học 2002 - 2003
(yêu cầu tất cả học sinh đội tuyển phải giải được)

Bài 1: FIGUER: (Ireland - 1994)

Cho .2 hình vuông A và B, Kích thước N X N ô đơn vị. Mỗi ô chứa một trong hai ký tự `+` hoặc dấu `.`. Hãy xét xem B có nhận được từ hính A bằng cách nào trong số những cách sau đây:
0 B=A
1. A quay 90o được B
2. A quay 180o được B
3. A quay 270o được B
4. A` là phép đối xứng A qua đáy ta được B
4.1 Thực hiện A`, sau đó quay 90o được B
4.2 Thực hiện A`, sau đó quay 180o được B
4.1 Thực hiện A`, sau đó quay 90o được B
4.2 Thực hiện A`, sau đó quay 180o được B
5. Các trường hợp trên không xẩy ra.

Vào: Tệp văn bản có tên là FIGUER.INP
- Dòng đầu là N. (1<=N<=50)
- Một dòng trống
- Tiếp theo là hình vuông A n dòng, mỗi dòng gồm N dấu `+` hoặc `.` được viết liền nhau
- Một dòng trống
- Tiếp đến là hình B gồm N dòng, mỗi dòng gồm N dấu `+` hoặc `.` được viết liền nhau.

Ra: Tệp văn bản FIGUER.OUT
m ( cách m thu được trong các cách trên)

Một số lưu ý khi làm các bài thi quốc gia:
( 1. Cố gắng không dùng lệnh Readln
2. Không dùng câu ấn phím bất kỳ để tiếp tục
(
Đặt tên file bài làm cũng tên File vào/ra phải đúng theo yêu cầu
Đặt tên hằng:
Ví dụ:
const vao=`FIGUER.INP`
ra= `FIGUER.OUT`

( Đặt kiểu dữ liệu
Type
ii: integer
ww: word;
bb:Byte;
cc: Char;
MN=51;
( M1=array[0..MN] of cc
M2= array [0..MN] of M1

( Cuối cùng là thủ tục RUN
Procedure RUN
Begin
thủ tục 1
thủ tục 2
............
END.

Như vậy chương trình chính chỉ cần:

BEGIN
RUN
END.




Phương pháp giải
1. Viết các hàm khiểm tra:
+ Đối xứng (hàm lật)
+ Quay 90o
+ Quay 180o
+Quay 270o
+ Hàm sánh

Ta chú ý lấy kết quả như sau:
a=b Kết quả là 0
a quay 90o được c ; nếu c=b kết quả là 1
c quay 90o được d; nếu d=b kết quả là 2
d quay 90o được e; nếu e=b kết quả là 3
lấy đối xứng a được c, nếu c=b ta được 4
c quay 90o được d, d=b ta được 4.1
d quay 90o được e, e=b ta được 4.2
e quay 90o được f, f=b ta được 4.3
nếu b không rơi vào các các trường hợp nói trên thì cho kết quả là 5.

Bài 2: Đỉnh độc đạo

Đỉnh độc đạo là gì:
Để trả lời câu hỏi trên trước hết ta xét ví dụ sau:
Ví dụ: Cho một hình vuông có cạnh độ dài N nguyên dương. Bảng này được chia thành N x N ô vuông bằng nhau, bằng các đường song song với các cạnh của hình vuông. Trên một ô vuông ghi một số nguyên dương <=1000. Từ một ô X ta có thể chuyển dịch đến một ô Y kề cạnh với nó nếu số ghi trong ô X bằng số trong ô Y cộng với một số chính phương nguyên dương.
Cho trước 2ô [Startrow, Sartcolumn] và [Desrow, Descolumn], một đường đi từ [Startrow, Sartcolumn] đến [Desrow, Descolumn] là một dãy các di chuyển qua các ô kề cạnh (theo nguyên tắc trên) bắt đầu từ ô [Startrow, Sartcolumn] và kết thúc tại ô [Desrow, Descolumn] . Ô khác với ô [Startrow, Sartcolumn] và [Desrow, Descolumn] mà mọi đường từ ô [Startrow, Sartcolumn] đến ô [Desrow, Descolumn] đều phải qua ô đó gọi là ô độc đạo.

Dữ liệu vào cho bởi file văn bản có tên là DOCDAO.INP có cấu trúc như sau:
- Dòng thứ nhất ghi 5 số nguyên dương lần lượt là số N, Startrow, Sartcolumn,[Desrow, Descolumn. N<=100.
Dòng thứ i+1, 1<=i<=N, ghi N số trong dòng thứ i của hình vuông theo thứ tự từ trái qua phải. Không phải kiểm tra tính đúng đắn của dữ liệu
Dữ liệu ra kết quả được ghi ra file văn bản DOCDAO.OUT thông tin về các ô độc đạo.
Mỗi dòng ghi 2 số là số dòng và số cột của từng ô độc đạo. Nếu không có đường đi từ ô [Startrow, Sartcolumn] đến [Desrow, Descolumn] hoặc không có ô độc đạo. thì thông báo: KHONG CO.


DOCDAO.INP


DOCDAO.OUT

Test 1
4 1 1 4 4
31 27 26 1
27 26 22 5
12 20 13 4
8 4 9 0
3 3


Test 2
4 1 1 3 4
1 29 26 1
29 26 19 5
8 19 14 7
12 20 14 5
KHONG CO



Phương pháp giải:
Để giải bài toán trên có thể có nhiều cách nhưng có lẽ dễ nhất là phương pháp dùng một mảng đếm Count [1..N,1..N] .
Ta sẽ tìm mọi cách đi từ ô bắt đầu [Startrow, Sartcolumn] đến ô kết thúc [Desrow, Descolumn]. Mỗi lần có đường đi giữa 2 ô đó ta tăng count[i,j] lên 1 Count[i,j]:=count[i,j]+1 với i,j là các ô nằm trên đườ ng đi giữa 2 ô.

Sau khi kết thúc quá trình trên, giả sử có M đường đi giữa 2 ô đã cho thì ô nào có count[i,j]=M thì ô đó nhất định là ô độc đạo.

Ngoài ra chúng ta có thể dùng cách sau:
Cứ mỗi bước đi (Step) ta thử xóa đi một ô và tìm cách đi từ ô bắt đầu [Startrow, Sartcolumn] đến ô kết thúc [Desrow, Descolumn]. nếu không đi được thì ghi nhận ô đó và sau cùng nếu giữa 2 ô xuất phát và kết thúc đó mà liên thông thì nhữ ô được ghi nhận là những ô độc đạo.


Một số bài toán xử lý dữ liệu lớn

Các bài toán có dữ liệu vào rất lớn thườn gây cho ta rất nhiều khó khăn, bởi vì nếu ta dùng cấu trúc mảng thông thường thì không thể lưu trữ số phần tử rất lớn được.
Để giải các bài toán có dữ liệu lớn ta phải tìm cấu trúc dữ liệu và giải thuật hợp lý. Đa số các bài toán trên phải dùng kỹ thuật vừa đọc vừa xử lý:

Bài toán 1:
Cho một tệp văn bản có n dòng (n(100000) mỗi dòng có độ dài không quá 255 ký tự. Trong đó có một dòng chỉ xuất hiện một lần duy nhất, còn các dòng còn lại có số lần xuất hiện là một số chẵn. hãy lập trình chỉ ra dòng đặc biệt đó.
Dữ liệu vào cho trong tệp DACBIET.INP , ghi các dòng thông tin và kết thúc bởi một dòng có 3 ký tự ###
Dữ liệu ra: tệp DACBIET.OUT , ghi ra dòng đặc biệt tìm được.

Ví dụ:
DACBIET.INP
DACBIET.OUT

- How are you?
- I`m fine
- How are you?
- My name is Beo
- I`m fine
###
My name is Beo


Giải: Với dữ liệu vào là rất lớn thì giải thuật đơn giản nhất là: cứ đọc một dòng bất kỳ sau đó so sánh với các dòng kế tiếp. Nếu không thấy xuất hiện quá một lần thì nó chính là dòng đặc biệt, ngước lại thì thực hiện với dòng kế tiếp. Nhưng nếu dòng đặc biệt là dòng cuối cùng thì số lần đọc tệp là rất lớn. nên thời gian chạy khá lâu. . Mặt khác ta không thể lưu trữ vào mảng được nên phải vừa đọc vừa xử lý.

Thuật toán: sử dụng phép toán XOR
Thực hiện
Kết quả

1 XOR 1
1 XOR 0
0 XOR 1
0 XOR 0
0
1
1
0


Dựa vào kết quả: Nếu A XOR B với số lần thực hiện là số chẵn thì cho ta A, vậy ta có thuật toán để giải bài này như sau:
- Dùng một mảng A[1..255] of Byte để lưu mã ASCII của các ký tự của dòng đặc biệt.
- Đọc một dòng S vào và gán A[i] :=A[i] XOR ORD(S[i]) (i chạy từ 1 đến Length(s);
- Viết ra dòng đặc biệt. Chương trình có thể viết như sau:
Program dong dacbiet;
Const fi=dacbiet.inp`
fo=`dacbiet.out`;
maxn=255;
var a: array[1..255] of byete;
i:integer; s:string;
f:text;
Procedure init;
Begin
fillchar(a,sizeof(a),0);
Assign(f,fi);
Reset(f);
End;

Program Main
Begin
While Not(eof(f)) do
begin
Readln(f,s);
if s= `###` then exit;
for i:=1 to length(s) do
a[i]:= a[i] xor ord[s[i]);
end;
End;

Procedure Done;
close(f);
Assign(f,fo);
Rewrite(f);
for i:=1 to maxn do
if a[i]<>0 then write(f,chr(a[i]));
close(f);
End;
BEGIN
init;
main;
done;
END.
Thuật toán này có độ phức tạp N nên chạy rất nhanh. Ngoài ra, bài toán này có thể giải bằng cách dùng mảng hai chiều , kích thước 255 X 255.

Bài toán 2: Cấp số cộng (đề thi HSG quốc gia 2001)
Cho một tệp văn bản gồm N (N rất lớn N<=100000) số nguyên a1, a2,a3,a4,..., an ; Với ai<=3000. Hãy tìm trong dãy con đó một dãy con dài nhất lập thành một cấp số cộng.
Dữ liệu vào: CAPSO.INP
- Dòng đầu ghi N
- N dòng tiếp theo ghi các số ứng với dãy A.
Dữ liệu ra: CAPSO.OUT
- Dòng dầu ghi số M là số phần tử và ghi công sai của cấp số cộng
- M dòng tiếp theo ghi chỉ số của các số thuộc cấp số cộng.

Bài 3: Hình chữ nhật tối đại