De thi chon doi tuyen quoc gia tinh Nghe An nam hoc2010 2011 ngay 2

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (84.17 KB, 3 trang )

(1)<div class='page_container' data-page=1>

Sở Giáo Dục & Đào Tạo NGhệ an Kỳ thi chọn đội tuyển dự thi
học sinh giỏi quc gia lp 12 THPT

năm học 2010 - 2011

Môn thi: tin học

Ngày thi: 08/10/2010

Thi gian: 180 phút (không kể thời gian giao đề)

Bài 1 (7 điểm). Thá vµ cµ rèt

Trong một mảnh vờn hình chữ nhật có các cạnh m, n nguyên dơng ngời ta trồng cà
rốt trong những ơ vng đơn vị có cạnh 1. Trong mảnh vờn này có một chú thỏ ở trong
một cái hang chiếm diện tích 1 ơ vng đơn vị. Chú thỏ cần xác định miền ngời ta đã
trồng cà rốt có diện tích lớn nhất trong mảnh vờn để đào một đờng hầm ngắn nhất đi
qua các ô vuông chung cạnh từ hang đến miền diện tích lớn nhất đó. (Miền đợc hiểu là
hình gồm một hoặc nhiều ơ vuông đơn vị chung cạnh. Hai miền khác nhau không cú
mt cnh ụ vuụng no chung).

Dữ liệu: Vào từ file văn bản CAROT.INP có cấu trúc:

Dòng đầu tiên ghi 4 sè M, N, x, y víi x, y lµ hàng và cột của hang thỏ trong mảnh
vờn (1 M, N  100).

 Trong M dßng tiÕp theo, dßng thø i cã N ký tù 0 hc 1 thể hiện hàng thứ i của
mảnh vờn với ý nghĩa 0 là không trồng cà rốt, 1 là có trồng cà rốt.

Kết quả: Ghi ra file văn bản CAROT.OUT nh sau:

 Dòng đầu ghi S là chiều dài của đờng hầm (S=0 nếu hang thỏ đang ở trên miền
trồng cà rốt có diện tích lớn nhất).

 Nếu S > 0 thì trong các dịng tiếp theo lần lợt ghi hàng và cột của các ô trên đờng
hầm bắt đầu từ hang thỏ đến miền diện tích lớn nhất trồng cà rốt.

VÝ dô:

CAROT.INP CAROT.OUT

6 6 1 1
0 0 0 0 1 1
0 0 0 0 1 1
0 0 0 0 1 1
0 0 0 0 1 1
0 0 0 0 1 1
1 1 1 0 0 0

4
1 1
1 2
1 3
1 4
1 5

Bài 2 (6 điểm). CUéC THI

Để ngời xem không nhàm chán khi xem cuộc thi trợt Patanh trên TV, những ngời làm
chơng trình khơng đa ra tồn bộ thông tin về cuộc thi mà chỉ đa ra một số chi tiết và
ng-ời xem cần tính tốn để xác định xem ai là ngng-ời chiến thắng. Các chi tiết đợc đa ra nh
sau: mỗi cuộc thi gồm hai vịng. Trong vịng đầu, có N ngời tham gia thi đợc đánh số
từ 1 đến N, cuộc thi bắt đầu theo thứ tự đó. Chúng ta đợc biết thời gian cần thiết để ngời
đầu tiên ở vịng đầu tiên (có số 1) hồn thành lần trợt. Cịn với mỗi ngời tiếp theo thì cho
biết sự chênh lệch thời gian giữa thời gian của ngời đó và thời gian của ngời hiện đang
dẫn đầu cuộc thi.

Chỉ có M ngời thi tốt nhất ở vòng một đợc vào vòng hai và họ bắt đầu vòng hai sắp
thứ tự theo thứ tự thành tích thời gian thi ở vịng một giảm dần (nghĩa là, ngời dẫn đầu
vịng một thì bắt đầu vòng hai cuối cùng). Trong vòng hai chúng ta đợc biết tổng thời
gian (của vòng thứ nhất và thứ hai) của ngời thi đầu tiên ở vòng này. Đối với những ngời
tiếp theo chúng ta biết đợc sự chênh lệch thời gian giữa tổng thời gian của ngịi đó và
tổng thời gian của ngời hiện đang dẫn đầu cuộc thi.

Hãy viết một chơng trình xác định ngời chiến thắng cuộc thi. Giả thiết rằng khơng
xảy ra khả năng hai ngời thi có cùng một thời gian (sau vòng một hay sau cả hai vịng).

Trang 1/3

§Ị chÝnh thøc

</div>
(2)<div class='page_container' data-page=2>

Thời gian của mỗi cuộc thi sẽ nằm trong khoảng từ 10 giây đến 300 giây. Tất cả thời
gian sẽ là số thực với không quá hai ch s thp phõn.

Dữ liệu: Vào từ file CUOCTHI.IN có cấu trúc:

Dòng đầu tiên chứa hai số nguyên N và M (3 M N 100).

Dòng thứ hai là thời gian của ngời có số 1 (ngời thi đầu tiên ở vòng đầu tiên).
N-1 dòng tiếp theo mô tả sự khác biệt thời gian.

Dòng tiếp theo chứa tổng thời gian của ngời đầu tiên trong vòng hai.
M-1 dòng sau mô tả sự khác biệt thời gian.

Kết quả: Ghi ra file CUOCTHI.OUT chỉ một dòng duy nhÊt chøa chØ sè cđa ngêi chiÕn

th¾ng.
VÝ dơ:

cuocthi.in cuocthi.out cuocthi.in cuocthi.out cuocthi.in cuocthi.out

3 3
25.13
+1.14
+2.18
45.08
+2.14
+3.11

3 4 3

29.18
+2.18
+0.05
+1.13
54.22
+1.23
+1.11

4 5 4

27.29
-1.02
+1.83
-0.43
+0.03
56.98
+1.83
-0.43
+0.03
 5

Bµi 3 (7 ®iĨm). ma thiên thạch

Trung tõm phịng chống thiên tai đợc các nhà khoa học thơng báo có một trận ma
thiên thạch sẽ ập xuống vùng a của Trái đất. Có N mảnh thiên thạch đánh số từ 1 đến N
sẽ rơi xuống vùng a. Tọa độ rơi v thời điểm rơi của mỗi mảnh thiên thạch đều đà ợc các
nhà khoa học dự báo chính xác. Để giảm thiểu thiệt hại, trung tâm cử đội cứu hộ đặc
biệt tới các điểm có thiên thạch rơi để phá hủy chúng trớc khi chúng kịp rơi xuống trái
đất. Thiên thạch sẽ không rơi xuống trái đất đợc nếu tại thời điểm rơi của thiên thạch

đội cứu hộ có mặt tại điểm rơi của thiên thạch. Thời gian phá hủy mỗi thiên thạch coi

nh không đáng kể. Đội cứu hộ xuất phát từ điểm có tọa độ (0, 0) tại thời điểm 0 và cứ
mỗi đơn vị thời gian thì đi đợc S đơn vị độ dài. Hỏi số lợng nhiều nhất các mảnh thiên
thạch mà đội cứu hộ có thể phá hủy? Chú ý rằng nếu đi với vận tốc 1 đơn vị độ dài/ 1
đơn vị thời gian thì khi đi từ điểm (0, 0) đến điểm (1, 1) đội cứu hộ sẽ mất 1.41 đơn vị
thời gian.

Dữ liệu: Vào từ file văn bản AEROLIFE.INP trong đó:

 Dßng thø nhÊt ghi hai sè nguyên N và S (1 N 5000, 1S 1000).

Tiếp theo là N dòng, mỗi dòng ghi 3 số nguyên Xi, Yi và Ti lần lợt là toạ độ Đề
các và thời điểm rơi của mảnh thiên thạch i sẽ rơi (-1000 < Xi , Yi < 1000, 1 T
1000000).

Kết quả: Ghi ra file AEROLIFE.OUT theo quy cách:

Dũng đầu chỉ gồm một số nguyên K là số mảnh thiên thạch nhiều nhất mà đội
cứu hộ có thể phá hủy đợc.

 K dòng sau mỗi dòng ghi số hiệu một mảnh thiên thạch mà đội cứu hộ có thể phá
hủy đợc.

VÝ dô:

AEROLIFE.INP AEROLIFE.OUT

5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2

</div>
(3)<div class='page_container' data-page=3>

Chó ý : - Các số trên cùng một dòng của các file dữ liệu vào/ra cách nhau một dấu c¸ch.

- Chơng trình bài1, bài 2, bài 3 phải đợc ghi lên đĩa với tên tơng ứng là bai1.pas,
bai2.pas, bai3.pas.

- Giám thị không giải thích gì thêm.

Họ và tên thÝ sinh:... Sè b¸o danh:...

</div>