CẦN THƠ
HỘI TIN HỌC VIỆT NAM
OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XII, 2003
Khối thi: chuyên tin
Thời gian làm bài: 180 phút
Ngày thi: 18 – 04 – 2003
Nơi thi: Đại học Cần Thơ
Tên bài Tên file chương trình Tên file dữ liệu Tên file kết quả
Tam giác TAMGIAC.??? TAMGIAC.INP TAMGIAC.OUT
Hình xoắn ốc SPIRAL.??? SPIRAL.INP SPIRAL.OUT
Ba thành phố COUNTRY.??? COUNTRY.INP COUNTRY.OUT
Hãy lập trình giải các bài sau đây:
Bài 1. Tam giác
Trên mặt phẳng cho N điểm có toạ độ nguyên A
i
(x
i
, y
1
), i = 1, 2, …, N. Mỗi
một trong số N điểm được tô bởi một trong số K mầu. Các mầu được đánh từ
1 đến K. Một tam giác với ba đỉnh là ba điểm có cùng mầu trong số N điểm
đã cho được gọi là tam giác cùng mầu.
Yêu cầu: Tìm một số lượng tam giác cân từng mầu.
Dữ liệu: Vào từ file văn bản TAMGIAC.INP:
 Dòng đầu tiên chứa hai số nguyên N và K được ghi cách nhau bởi dấu
cách; (1<N200; 1K4);
 Dòng thứ i trong số N dòng tiếp theo chứa 3 số x
i
, y
i

-1 -1 1
Minh hoạ
Bài 2. Hình xoắn ốc
Bằng cách viết liên tiếp các số tự nhiên từ 1 tới N ta nhận được một dãy các
số. Ví dụ với N =18 ta có dãy các chữ số: 123456789101112131415161718.
Sau đó điền dãy chữ số này vào các điểm nguyên của mặt phẳng toạ độ theo
chiều xoắn ốc bắt đầu từ điểm (0,0) như sơ đồ sau:
y
1
1 5 4 3 1
4 6 1 2 0
1 7 8 9 1 x
5 1 6 1 7
Như vậy với một số N cho trước một số điểm nguyên của mặt phẳng toạ độ
cho chứa một chữ số.
Yêu cầu: Cho hai số nguyên x và y, hãy:
a. Tìm số tự nhiên N lớn nhất sao cho điểm (x,y) chưa có chữ số.
b. Giả sử điểm (x,y) đã có chữ số. Hãy tìm chữ số K được điền tại điểm
(x,y).
Dữ liệu: Vào từ file văn bản SPIRAL.INP gồm một dòng chứa 3 số nguyên q,
x và y, trong đó q = 1 nếu là yêu cầu a) và q = 2 nếu là yêu cầu b), còn x và y
có giá trị tuyệt đối không vượt quá 20000.
Kết quả: Ghi ra file văn bản SPIRAL.OUT:
Nếu q = 1 hãy ghi ra số N (kết quả câu a), còn nếu q = 2 hãy ghi ra chữ số
K (kết quả câu b).
Ví dụ:
SPIRAL.INP SPIRAL.OUT
1 -2 2 1 2
SPIRAL.INP SPIRAL.OUT
2 -2 2 3

 Dòng đầu tiên chứa số nguyên N (3N10000).
 Tiếp theo là N dòng mô tả thông tin về các thành phố. Dòng thứ i chứa
các số: K
i
số nguyên là các chỉ số thành phố này.
Dữ liệu đảm bảo là có con đường nối A với B thì cũng có con đường nối B
với A, đồng thời với mọi cặp thành phố đều thực hiện điều kiện đã nêu.
Kết quả: Ghi ra file văn bản COUNTRY.OUT một số nguyên là độ giãn cách
giữa ba thành phố tìm được.
Ví dụ:
COUNTRY.INP COUNTRY.OUT
5
1 3
1 3
2 1 2 4
2 3 5
1 4
8