Đề ôn luyện HSG

Một số bài toán bồi dưỡng đội tuyển hsg Tin học
(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