Đề thi chọn học sinh giỏi quốc gia lớp 12 THPT môn Tin - vòng 2 - năm học 2011 - 2012

SỞ GD&ĐT QUẢNG BÌNH ĐỀ THI CHÍNH THỨC SỐ BÁO DANH : ............... KỲ THI CHỌN ĐỘI TUYỂN CHÍNH THỨC DỰ THI CHỌN HSG QUỐC GIA LỚP 12 THPT NĂM HỌC 2011 - 2012 Môn thi: TIN HỌC - VÒNG 2 Khóa ngày: 24/11/2011 Thời gian: 180 phút (Không kể thời gian giao đề) Sử dụng ngôn ngữ lập trình Turbo Pascal để giải các bài toán sau đây: Câu 1: (6,0 điểm) Đường chạy địa hình ROUTE.PAS Trong Đại hội thể thao Quốc tế, người ta dự định sẽ tổ chức một môn chạy bộ địa hình. Đường chạy địa hình là một đường kép kín, nơi bắt đầu cũng là nơi kết thúc. Đường chạy có độ dài N (mét), mỗi mét có một độ cao h (cm) so với mực nước biển. Yêu cầu: Hãy đếm số lượng đường bằng, số lượng đường dốc lên và số lượng đường dốc xuống của đường chạy địa hình, tính từ nơi xuất phát. Dữ liệu vào: Cho trong file văn bản ROUTE.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, là chiều dài của đường chạy địa hình. - Dòng 2: Ghi N số nguyên dương hi là độ cao của mét thứ i trên đường chạy địa hình. Các số được ghi cách nhau ít nhất một dấu cách. (3 ≤ N ≤ 30000; 1 ≤ hi ≤ 30000). Dữ liệu ra: Ghi ra file văn bản ROUTE.OUT, theo cấu trúc như sau: - Dòng 1: Ghi ba số nguyên dương x y z, trong đó x là số lượng đoạn đường bằng, y là số lượng đoạn đường dốc lên, z là số lượng đoạn đường dốc xuống của đường chạy địa hình. Các số được ghi cách nhau ít nhất một dấu cách. Ví dụ: ROUTE.INP ROUTE.OUT 6 1 2 2 20 23 60 50 50 12 Câu 2: (7,0 điểm) Điều khiển Robot tắt động cơ. ROBOT.PAS Trong một xưởng sản xuất, có N máy được bố trí trên một đoạn đường thẳng. Một trung tâm điều hành nằm ở đầu trái của đoạn đường. Các máy được đánh số từ 1 đến N theo thứ tự từ trái sang phải. Biết khoảng cách từ máy thứ i đến trung tâm điều hành là di. Mỗi máy i có mức tiêu thụ điện năng Ci trên một đơn vị thời gian. Để tắt N máy, người ta sử dụng một Robot. Ban đầu, Robot chỉ được đặt tại vị trí của một máy nào đó. Robot có thể di chuyển về bên trái hoặc về bên phải dọc theo đoạn đường để tắt máy. Số lần đổi hướng di chuyển của Robot là không quá 1. Biết rằng: Robot di chuyển 1 đơn vị chiều dài mất 1 đơn vị thời gian. Robot di chuyển đến máy nào thì tắt ngay máy đó và không mất thời gian dừng lại để tắt máy. Yêu cầu: Hãy xác định vị trí đặt Robot khi xuất phát để tổng số điện năng tiêu thụ của N máy là nhỏ nhất (tính từ thời điểm đặt Robot đến khi Robot tắt xong tất cả các máy). Dữ liệu vào: Cho trong file văn bản ROBOT.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, là số lượng máy tiêu thụ điện năng. (1 ≤ N ≤ 300) - Dòng 2: Ghi N số nguyên dương di, là khoảng cách từ máy thứ i đến trung tâm điều hành. Các số được ghi cách nhau ít nhất một dấu cách. (1 ≤ di ≤ 3000) - Dòng 3: Ghi N số nguyên dương Ci, là mức tiêu thụ điện năng của máy i trên một đơn vị thời gian. Các số được ghi cách nhau ít nhất một dấu cách. (1 ≤ Ci ≤ 3000) Dữ liệu ra: Ghi ra file văn bản ROBOT.OUT, theo cấu trúc: - Dòng 1: Ghi hai số nguyên dương V M. Trong đó: M là chỉ số của máy, nơi mà ROBOT xuất phát; V là tổng số điện năng nhỏ nhất mà N máy đã tiêu thụ tính từ khi Robot xuất phát tại M cho đến khi tắt hết N máy. Hai số được ghi cách nhau ít nhất một dấu cách. (1 ≤ V ≤ 2147483647). Ví dụ: ROBOT.INP ROBOT.OUT 3 10 20 25 5 1 10 80 3 Câu 3: (7,0 điểm) Thuê phòng hội thảo ROOM.PAS Một ông chủ có một căn phòng rất rộng dùng để cho thuê. Rất nhiều khách hàng muốn thuê để tổ chức hội thảo. Ông chủ không đưa ra một mức giá cho thuê cụ thể mà yêu cầu khách hàng tự đăng ký vào một phiếu thuê phòng. Mỗi phiếu đăng ký gồm có các thông tin chính sau: + Thời điểm bắt đầu thuê: Bi + Thời gian thuê: Ti + Số tiền phải trả: Mi Hiện nay, ông chủ đã nhận được N phiếu đăng ký thuê. Ông không nhận thêm phiếu đăng ký nào nữa mà chỉ xem xét và chọn khách hàng để cho thuê. Yêu cầu: Hãy giúp ông chủ xác định cần làm hợp đồng với những khách hàng nào để tổng số tiền thu được là lớn nhất. Biết rằng, khoảng thời gian thuê của hai người khách bất kỳ không được giao nhau kể cả điểm mút. Dữ liệu vào: Cho trong file văn bản ROOM.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, là số lượng phiếu đăng ký thuê phòng. (0 < N ≤ 16000) - Dòng thứ i trong N dòng tiếp theo: Ghi 3 số nguyên dương Bi Ti Mi là thông tin trên phiếu đăng ký của khách hàng thứ i. Các số được ghi cách nhau ít nhất một dấu cách. (0 < Mi, Bi, Ti ≤ 16000) Dữ liệu ra: Ghi ra file văn bản ROOM.OUT, theo cấu trúc như sau: - Dòng 1: Ghi số nguyên dương Q, là tổng số tiền lớn nhất thu được trong phương án cho thuê của ông chủ căn phòng. (0 < Q < 2147483647) Ví dụ ROOM.INP ROOM.OUT 3 50 300 200 30 230 100 270 350 150 250 Giới hạn thời gian thực hiện chương trình không quá 2 giây đối với mỗi bộ dữ liệu vào. === Hết ===