Đề thi chọn học sinh giỏi Lớp 12 THPT môn Tin học - Năm học 2012-2013 - Sở GD&ĐT Ninh Bình (Đề 2) (Có đáp án)

ĐỀ THI CHÍNH THỨC
SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT 
Kỳ thi thứ nhất - Năm học 2012 – 2013
MÔN: TIN HỌC
Ngày thi: 10/10/2012
(Thời gian làm bài: 180 phút)
Đề thi gồm 04 câu, trong 02 trang
Tổng quan đề thi:
Câu
Tên file bài làm
Tên file Input
Tên file Otput
Thời gian chạy
1
TOUR.PAS
TOUR.INP
TOUR.OUT
1 giây/test
2
HAIVAN.PAS
HAIVAN.INP
HAIVAN.OUT
1 giây/test
3
FROG.PAS
FROG.INP
FROG.OUT
1 giây/test
4
EC.PAS
EC.INP
EC.OUT
1 giây/test
Câu 1: Thăm quan.
 Có N đoàn khách du lịch được đánh số từ 1 đến N đang chờ Công ty du lịch Ninh Bình đưa đi thăm quan theo hợp đồng. Đoàn thứ i sẽ đi tới thăm quan ở địa điểm cách trụ sở Công ty di km. Công ty có M xe khách (N≤ M) đánh số từ 1 tới M, xe thứ j có mức tiêu thụ xăng là vj lít/km. 
Yêu cầu: Hãy chọn N xe và bố trí để đưa các đoàn đến địa điểm thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng lượng xăng cần phải sử dụng là ít nhất.
Dữ liệu: Cho trong file TOUR.INP
Dòng 1 chứa hai số nguyên N, M ( N≤ M ≤ 500).
Dòng 2 chứa N số nguyên dương d1, d2,..., dN (di < 104).
Dòng 3 chứa M số nguyên dương v1, v2, ..., vM (vi < 104).
Kết quả: Ghi ra file TOUR.OUT một số nguyên là lượng xăng ít nhất cần cung cấp cho các xe.
Ví dụ:
TOUR.INP
TOUR.OUT
3 4
7 5 9
17 13 15 10
256
Câu 2: An toàn đường hầm Hải Vân.
	Hầm đèo Hải Vân nối liền hai địa danh nổi tiếng miền trung Việt Nam là Huế và Đà Nẵng. Theo quy định, xe ô tô đi trong đường hầm không được vượt nhau. Đầu năm 2012 (là năm an toàn giao thông), ban quản lý đã đặt camera theo dõi xe ô tô vào và ra đường hầm. Có N xe ô tô đánh số từ 1 tới N được camera ghi nhận đi vào đường hầm (bên địa phận Huế) và ra khỏi đường hầm (bên địa phận Đà Nẵng). 
Yêu cầu: Dựa vào thứ tự các xe vào và ra khỏi đường hầm, xác định số lượng xe ra đường hầm không đúng thứ tự như khi đi vào và số lượng những xe chắc chắn đã vượt xe khác trong đường hầm.
Dữ liệu: Cho trong file HAIVAN.INP:
Dòng 1 chứa số nguyên N ( N ≤ 105).
Dòng 2 chứa N số lần lượt là chỉ số các xe theo thứ tự đi vào đường hầm.
Dòng 3 chứa N số lần lượt là chỉ số các xe theo thứ tự đi ra khỏi đường hầm.
Kết quả:Ghi ra file HAIVAN.OUT trên 02 dòng:
Dòng 1 chứa số nguyên K - số xe đi ra không đúng thứ tự như khi vào đường hầm.
Dòng 2 chứa số nguyên M - số xe đã vượt xe khác trong hầm.
Nếu không có xe nào phạm luật thì mỗi dòng ghi một số 0.
Ví dụ: 
HAIVAN.INP
HAIVAN.OUT
Giải thích
5
1 2 3 4 5
1 4 5 3 2
4
3
Xe 2, 3, 4, 5 ra không đúng thứ tự
Xe 3, 4, 5 đã vượt xe 2
Chú ý: Trong 60% số test có n < 200; Trong mỗi test, chỉ làm đúng 1phần vẫn được cho điểm phần đó.
Câu 3: Chú ếch.
 Chú ếch con phải giải quyết một chuyện phức tạp: có một hàng N lá bông súng trên mặt nước đánh số từ 1 đến N từ trái qua phải (2 ≤ N ≤ 105), khi chú ếch đang ngồi ở lá thứ m mỗi bước chú có thể nhảy sang một trong k lá bông súng khác có thứ tự là m + pi (i = 1, 2,..,k; k ≤ 1000). Chú ếch của chúng ta ban đầu ở lá a và cần di chuyển trên các lá bông súng để đến bắt con ruồi ở lá b (1 ≤ a, b ≤ N, a ≠ b).
Yêu cầu: Cho n, a, b và các bước nhảy ếch có thể thực hiện. Hãy chỉ ra số bước nhảy ít nhất để ếch đến bắt được ruồi tại lá b. 
Dữ liệu: Cho trong file FROG.INP:
Dòng 1 chứa 4 số nguyên N, k, a và b.
Trên k dòng sau mỗi dòng là một số nguyên pi (|pi| < N). 
Kết quả: Ghi ra file FROG.OUT số bước nhảy ít nhất tìm được. Nếu không có cách nhảy ghi -1.
 Ví dụ:
FROG.INP
FROG.OUT
5 2 2 3
2
-1
2
Chú ý: Trong 60% số test có n < 30.
Bµi 4: Ðp cäc.
 Một công trình xây dựng đang cần thi công việc ép N chiếc cọc. Người ta sử dụng một chiếc máy ép cọc. Mỗi lần sử dụng, máy có thể ép được những cọc thuộc hình tròn bán kính R, tâm là vị trí máy. Giả thiết rằng khu vực thi công nằm trong hệ trục Oxy và máy chỉ được đặt trên trục Ox tại các điểm có tọa độ nguyên. Do mỗi lần vận hành máy rất vất vả tốn kém nên các thợ máy muốn xác định số lần ép cọc ít nhất có thể. 
Yêu cầu: Cho biết tọa độ của N chiếc cọc, hãy xác định số lần sử dụng máy ít nhất có thể ép được tất cả N cọc.
Dữ liệu: Cho trong file EC.INP:
Dòng 1 chứa 2 số nguyên dương N và R. (N≤105, R ≤103).
Trong N dòng tiếp theo, mỗi dòng chứa 2 số nguyên xi và yi thể hiện tọa độ cọc thứ i 
 ( 0 ≤xi ≤109 ; | yi| ≤ R).
Kết quả: Ghi ra file EC.OUT một số nguyên là số lần ép cọc ít nhất tìm được.
Ví dụ:
EC.INP
EC.OUT
4 3
2 2
4 -2
7 2
8 1
2
Chú ý: Trong 60% số test tất cả các cọc thẳng hàng và đều nằm trên trục Ox với n ≤ 1000, R ≤ 100, các tọa độ nhỏ hơn 104.
-----------------------------Hết--------------------------
Họ và tên thí sinh :....................................................... ..Số báo danh .............................
Họ và tên, chữ ký: Giám thị 1:......................................................................................................
 Giám thị 2:.......................................................................................................