Sở Giáo Dục & Đào Tạo KỲ THI OLYMPIC TRUYỀN THỐNG 30/4
TP. HỒ CHÍ MINH LẦN X – NĂM 2004
(( ((
Trường THPT Chuyên Môn thi : TIN HỌC - Khối : 11
Lê Hồng Phong Ngày thi : 10-04-2004 Thời gian làm bài : 180 phút
Bài 1: Đa giác
Cho N đa giác lồi thoả các tính chất sau :
+ Với 2 đa giác bất kỳ luôn có một đa giác mà mọi điểm của nó nằm trong đa giác kia.
+ Các cạnh của chúng không có điểm chung.
Bài toán đặt ra là: Với mỗi đa giác i , có bao nhiêu đa giác bao nó ? ( i nằm trong bao nhiêu đa giác ?)
Yêu cầu:
Dữ liệu vào : Ghi trong tập tin văn bản DAGIAC.INP :
Dòng đầu tiên ghi số tự nhiên N ( 3 <= N <= 10000 ).
Trên N dòng tiếp theo:
dòng thứ i+1 ghi thông tin về đa giác có số hiệu thứ i. Bao gồm Số đầu tiên Si là số đỉnh của đa giác ( Si >=3 ) ; Si cặp số nguyên tiếp theo lần lượt là hoành độ và tung độ các đỉnh của đa giác.
Các số trên cùng dòng cách nhau bởi ít nhất một khoảng trắng.
Dư liệu ra: Ghi trong tập tin văn bản DAGIAC.OUT
Gồm N dòng:
Dòng thứ i : ghi số lượng đa giác bao đa giác i..

Ví dụ:
DAGIAC.INP
DAGIAC.OUT

4
4 1 1 15 1 15 8 1 8
4 9 3 9 6 4 6 4 3
4 3 2 11 2 11 7 3 7
3 8 4 8 5 6 5
0
2
1
3









Bài 2: Xếp dải băng
Cho một dải băng gồm 2k ô, kích thước ô như nhau và trên các ô lần lượt ghi các số 1, 2, ...., 2k ( ghi từ trái sang phải ). Người ta lần lượt gấp đôi dải băng theo chiều từ phải sang (độ dài sẽ giảm một nửa, số lớp sẽ tăng gấp đôi) cho đến khi dải băng có 2k lớp. Hỏi ô mang số N nằm ở lớp thứ mấy (tính từ dưới lên)? Cho k nguyên dương (k <=30).

Chẳng hạn, xét trường hợp k = 3, N =5:
B1: 1 2 3 4 5 6 7 8
B2 8 7 6 5
1 2 3 4
B3: 4 3
5 6
8 7
1 2
B4: 2
7
6
3
4
5
8
1
Số 5 ở lớp thứ 3.

Dữ liệu vào:
Cho trong tập tin văn bản XEPSO.IN, gồm hai số k và N.

Dữ liệu ra:
Cho trong tập tin văn bản XEPSO.OUT, gồm một số nguyên duy nhất chỉ số thứ tự lớp của ô chứa số N.

Ví dụ:

XEPSO.IN
XEPSO.OUT

3 5
3


Baì 3 : ( Bài toán trong vườn trẻ )
Trong vườn trẻ , có các nhóm trẻ đang chơi ở những sân chơi khác nhau cùng với cô giáo hướng dẫn (mỗi sân chơi chỉ cho 1 nhóm , mỗi nhóm do 1 cô giáo hướng dẫn ) Mỗi sân chơi có lối đi nối với 1 hay nhiều sân chơi khác. Một hay nhiều sân chơi có lối đi nối với sân chơi chính. số sâm chơi không có học sinh Có cộng có p lối đi .
Có đúng 26 sân chơi được đặt tên là từ ‘a’ đến ‘z’ , sân chơi chính tên là ‘z’ và theo qui định chung không có nhóm trẻ nào được chơi ở đó. Trên bảng theo dõi ở sân chơi chínhù., sân chơi nào hiện đang có 1 nhóm trẻ đang chơi sẽ được gán tên là chữ in hoa ( vd : Sân chơi có tên là ‘y’ hiện đang có 1 nhóm trẻ đang chơi thì trên bảng theo dõi sẽ được gán tên là ‘Y’).
Khi có thông báo đến giờ nghỉ của vườn trẻ , các nhóm sẽ theo cô giáo hướng dẫn của mình đi nhanh về sân chính bằng các lối đi rồi mới được bố mẹ đến đón về – các cô giáo luôn luôn tìm ra con đường ngắn nhất để dẫn các cháu đi . (Tất nhiên ,đường đi mà các cô giáo chọn có thể đi ngang qua 1 số sân chơi khác ). Giả sử tốc độ đi của các nhóm là như nhau , và các lối đi đủ rộng để không có nhóm nào phải tạm dừng lại ( tránh nhau ) khi đi – Người ta cần biết sau khi phát thông báo thì nhóm trẻ hiện đang chơi ở sân chơi nào về tới