Đề thi học sinh giỏi tỉnh Cà Mau lớp 12 năm 2011 môn Tin học Sở GD&ĐT Cà Mau

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ố.

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.

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 a_i.

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.

Download tài liệu để xem thêm chi tiết