ĐỀ THI HỌC SINH GIỎI
NĂM HỌC 2005 − 2006
Môn : TIN HỌC
Thời gian làm bài : 180 phút
Ngày thi thứ nhất : 14 tháng 11 năm 2005
TỔNG QUAN BÀI THI
Tên bài Tên chương trình File dữ liệu vào File kết quả
BÀI 1 Chuỗi tam giác TG.PAS TG.INP TG.OUT
BÀI 2 Dãy cân bằng DAYCB.PAS DAYCB.INP DAYCB.OUT
BÀI 3 Biến đổi dãy số BDDAY.PAS BDDAY.INP BDDAY.OUT
Bài 1. Chuỗi tam giác
Trên mặt phẳng cho N tam giác ( 1 ≤ N ≤ 5 000). Các tam giác không có cạnh nào giao nhau
(hoặc nằm lồng nhau hoặc không có điểm chung).
Yêu cầu : Hãy viết chương trình tìm chuỗi dài nhất các tam giác lồng nhau trong số N tam giác
đã cho trên.
Dữ liệu vào : Cho trong file văn bản TG.INP có nội dung như sau:
• Dòng đầu chứa số N
• Mỗi dòng trong N dòng tiếp theo chứa 6 số nguyên x
1
, y
1
, x
2
, y
2
, x
3
, y
3
, là tọa độ của các
đỉnh tam giác tương ứng.

N
là không khả thi. Ta có
thể xem mỗi phần tử của T
N
là một số trong hệ nhị phân gồm 2N chữ số. Giả sử T
N
có K phần
tử. Để thuận lợi cho việc xử lý, người ta xếp các dãy số thuộc T
N
theo thứ tự tăng dần của giá
trị. Dãy đầu tiên (nhỏ nhất) được đánh số là 0 và chuỗi cuối cùng (lớn nhất) được đánh số là K-
1. Ví dụ, khi N = 2, ta có K = 6 và các dãy tương ứng thuộc T
2
là (theo thứ tự từ 0 đến 5) 0011,
0101, 0110, 1001, 1010 và 1100.
Yêu cầu : Cho N và một số I, hãy cho biết dãy có số thứ tự I trong tập T
N
.
Dữ liệu vào : Cho trong file văn bản DAYCB.INP chứa 2 số N và I nằm trên cùng một dòng.
Các số cách nhau bởi khoảng trống.
Kết quả ra : Ghi vào file văn bản DAYCB.OUT chứa dãy tương ứng tìm được hoặc số -1
(trong trường hợp I < 0 hoặc I ≥ K).
Ví dụ :
DAYCB.INP DAYCB.OUT
2 2 0110
Bài 3 : Biến đổi dãy số
Cho một dãy A gồm N số nguyên A
1
, A
2