Thursday, March 16, 2017
SỞ
GIÁO DỤC & ĐÀO TẠO ĐỀ THI HỌC
SINH GIỎI VÒNG TỈNH LỚP 12 THPT
CÀ MAU NĂM HỌC 2010-2011
Môn thi: Tin học
Ngày thi: 14 – 11
– 2010
Thời gian: 180
phút (Không
kể thời gian giao đề)
Hãy lập trình giải các bài toán sau:
Bài 1 (6 điểm):
Với số nguyên dương Y cho trước, xét tập hợp X(Y) gồm tất cả các phân số
có giá trị thuộc đoạn [0, 1] với mẫu số không lớn hơn Y.
Ví dụ:
với Y = 7, ta có các phân số sau:
0/1; 1/7; 1/6; 1/5; 1/4; 2/7; 1/3;
2/5; 3/7; 1/2;
4/7; 3/5; 2/3; 5/7; 3/4; 4/5; 5/6;
6/7; 1/1
Cho trước số nguyên dương Y, viết
chương trình in ra mọi phân số tối giản thuộc X(Y) theo thứ tự tăng dần của giá
trị.
- Dữ liệu vào: file BAI1.INP
Gồm một dòng duy nhất ghi số nguyên dương Y ≤ 100.
- Kết quả: file BAI1.OUT
Gồm một số dòng, mỗi dòng ghi
một phân số thuộc X(Y) theo thứ tự tăng dần, mỗi phân số viết dưới dạng tử số/mẫu số.
Ví dụ:
BAI1.INP BAI1.OUT
7 0/1
1/7
1/6
1/5
1/4
2/7
1/3
2/5
3/7
1/2
4/7
3/5
2/3
5/7
3/4
4/5
5/6
6/7
1/1
Bài 2 (7 điểm):
Khi làm việc trong môi trường Windows, ta thường mở nhiều cửa sổ. Mỗi cửa
sổ là một hình chữ nhật có các cạnh song song với các cạnh màn hình, gồm một số
ô trong một lưới 1024 x 768 ô vuông đơn vị. Các dòng của lưới này được đánh số
1, 2, … 1024 từ bên trên xuống dưới, các cột đánh số 1, 2, …, 768 từ bên trái
sang phải. Như vậy, mỗi cửa sổ được xác định bởi vị trí ô trái trên và ô phải
dưới. Nếu bấm chuột vào ô phải trên của cửa sổ, cửa sổ sẽ bị đóng lại.
Trong quá trình mở các cửa sổ, cửa sổ mở sau có thể che một phần hoặc
hoàn toàn cửa sổ mở trước; một cửa sổ chỉ có thể đóng được nếu ô phải trên của
nó không bị che.
Cho dãy X cửa sổ với tên 1, 2, …, X được mở ra theo thứ tự đó, cần phải
dùng ít nhất bao nhiêu lần đóng cửa sổ để có thể đóng được cửa sổ 1?
- Dữ liệu vào: file BAI2.INP, trong đó:
+ Dòng thứ nhất ghi số X ≤
100.
+ Tiếp theo là X dòng, dòng thứ
I ghi bốn số A, B, C, D với ý nghĩa ô trái trên của cửa sổ thứ I là [A,B], ô phải
dưới của cửa sổ thứ I là [C,D].
- Kết quả: file BAI2.OUT như sau:
+ Dòng thứ nhất ghi số N là số
lần đóng cửa sổ, dòng thứ hai ghi N số hiệu cửa sổ lần lượt đóng.
Ví dụ:
BAI2.INP BAI2.OUT
4 4
4
1 6 3 3 2
4 1
2
2 5 4
1
2 7 5
3
1 7 3
Bài 3 (7
điểm):
Cho N điểm a1,
a2, ..., aN trên mặt phẳng. Các điểm đều có toạ độ nguyên
và không có 3 điểm bất kì nào thẳng hàng. Hãy viết chương trình:
a) Xác định một đa giác không tự cắt có đỉnh
là một số điểm trong các điểm đã cho chứa tất cả các điểm còn lại và có chu vi
nhỏ nhất.
b) Tính diện tích đa giác đó.
- Dữ liệu vào: Cho trong file BAI3.INP
gồm N+1 dòng
+ Dòng 1 chứa số N;
+ Dòng i+1 (1 ≤ i ≤ N) chứa 2 số xi
và yi là toạ độ của ai.
Các số trên cùng một dòng ghi cách nhau ít nhất
một dấu cách.
- Kết quả: Xuất ra file BAI3.OUT dưới
dạng
+ Dòng 1 ghi 3 số: K, V, S (với K là số đỉnh đa
giác tìm được, V là chu vi và S là diện tích của đa giác đó).
+ Dòng i+1 (1 ≤ i ≤ K) ghi toạ độ của đỉnh đa
giác.
