Tài liệu đề thi học sinh giỏi tin cấp tỉnh

SỞ GIÁO DỤC VÀ ĐÀO TẠO KHÁNH HÒA  ĐỀ THI CHÍNH THỨC KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH NĂM HỌC 2009-2010  Môn thi : TIN HỌC - THPT (Bảng B) Ngày thi : 06/4/2010 (Thời gian : 180 phút – không kể thời gian phát đề)  BÀI 1 : (5 điểm) Viết chương trình cho nhập vào một dãy gồm N các ký tự: D, X, T bất kỳ. In ra màn hình dãy đã được sắp xếp theo qui luật T xếp trước rồi đến D và cuối cùng là X. Với N được nhập từ bàn phím. Ví dụ : Với N = 8 - Dãy ban đầu nhập : X T T D X D X T - Dãy sau khi được sắp xếp : T T T D D X X X BÀI 2 : (5 điểm) Viết chương trình cho nhập vào một số nguyên N (4  N  20), cho sinh ngẫu nhiên một dãy gồm N số nguyên có giá trị trong khoảng [1..100]. In ra màn hình cặp số kề nhau trong dãy có khoảng cách lớn nhất. Cho biết khoảng cách và vị trí của cặp số tìm được. Yêu cầu có kiểm tra điều kiện nhập N. Ví dụ : Với N = 6 - Giả sử dãy số được sinh ra là: 5 5 8 4 3 1 - Thì cặp số cần tìm là: 8 và 4, có khoảng cách là 4, tại vị trí 3 và 4. BÀI 3 : (5 điểm) Cho một số tự nhiên N và mảng số thực A kích thước 4xN chứa dữ liệu về N hình chữ nhật: (a[1,i], a[2,i]) và (a[3,i], a[4,i]) là toạ độ góc trái trên và góc phải dưới của hình chữ nhật thứ i. Hỏi có điểm nào trong mặt phẳng toạ độ thuộc tất cả các hình chữ nhật đã cho không? Hãy lập trình để giải bài toán đó. Dữ liệu vào: Từ tập tin văn bản BAI3.INP có qui cách như sau : - Dòng đầu tiên ghi số N (1  N  50); - Dòng thứ i trong N dòng tiếp theo, mỗi dòng gồm 4 số là các toạ độ a[1,i], a[2,i], a[3,i], a[4,i] tương ứng, các số được viết cách nhau ít nhất một khoảng trắng. Dữ liệu ra: Tập tin văn bản BAI3.OUT - Tất cả các toạ độ đã cho trong tệp BAI3.INP - Ghi giá trị điểm tìm được hoặc thông báo không có điểm nào thuộc tất cả hình chữ nhật. Ví dụ : BAI3.INP BAI3.OUT 3 3.0 1.0 6.0 4.0 3164 1.0 2.0 4.0 6.0 1246 2.0 3.0 5.0 5.0 2355 Co diem thuoc tat ca cac hinh chu nhat: 3.0 3.0 Trang 1 BAI3.INP BAI3.OUT 3 3344 1122 5566 3.0 3.0 4.0 4.0 1.0 1.0 2.0 2.0 5.0 5.0 6.0 6.0 Khong co diem nao thuoc tat ca cac hinh chu nhat BÀI 4 : (5 điểm) Ghế ngồi trong hội trường phục vụ cuộc thi “Tiếng hát học sinh sinh viên” được chia thành từng lô, mỗi lô gồm M hàng đánh số từ 1 đến M, mỗi hàng có N ghế đánh số từ 1 đến N từ trái qua phải (4  M, N  20). Ghế có 3 loại: màu trắng (W), màu xanh (B) và màu đỏ (R). Theo thiết kế, mỗi lô chỉ lắp ghế cùng một màu, nhưng vì không nắm được thiết kế, bộ phận thi công đã lắp các ghế một cách ngẫu nhiên mà không quan tâm đến màu của chúng. Do thời điểm khai mạc cuộc thi đến quá gần, không có đủ thời gian để tháo dỡ lắp đặt lại các ghế, nên người ta dựng một Robot sơn trang trí để sơn lại các ghế trong hội trường. Robot hoạt động theo nguyên tắc sau : - Nếu hai ghế kề nhau trên cùng một hàng có màu khác nhau thì robot sẽ sơn lại cặp ghế này bởi màu thứ ba. - Nếu hai hàng ghế kề nhau có màu khác nhau, nhưng ghế ở mỗi hàng là cùng màu, thì robot sẽ sơn lại ghế của hai hàng này thành màu thứ ba, trong trường hợp này, có N cặp ghế được sơn lại. Dựa vào ảnh chụp toàn cảnh lô ghế, bạn được đề nghị cài đặt một chương trình điều khiển robot hoạt động theo nguyên tắc đã nêu để sơn lại các ghế sao cho tất cả các ghế trong lô có cùng một màu đồng thời tổng số lượt cặp ghế phải sơn là càng ít càng tốt. Ví dụ: Với M = 4, N = 4 và bức tranh toàn cảnh của lô ghế là: BBBR BBBB WWWW WWWW Có 10 lượt cặp ghế được robot sơn theo chương trình điều khiển sau: BBBR BBBB WWWW WWWW  BBWW BBBB WWWW WWWW  BRRW BBBB WWWW WWWW  BRBB BBBB WWWW WWWW  BWWB BBBB WWWW WWWW  RRWB BBBB WWWW WWWW  RRRR BBBB WWWW WWWW  WWWW WWWW WWWW WWWW Yêu cầu : Tìm cách điều khiển robot thoả mãn các yêu cầu đặt ra. Dữ liệu vào: từ tập tin văn bản BAI4.INP có cấu trúc:  Dòng đầu tiên chứa 2 số nguyên M, N.  M dòng sau mỗi dòng chứa một xâu N ký tự, mỗi ký tự là W, B hoặc R, dòng thứ i+1 thể hiện màu các ghế trong hàng thứ i. Dữ liệu ra: Đưa ra tập tin văn bản BAI4.OUT: - Dòng đầu tiên chứa k là tổng số lượt cặp ghế phải sơn theo cách điều khiển tìm được. - Các dòng tiếp theo mô tả cách điều khiển robot sơn ghế, mỗi dòng có một trong hai dạng (tương ứng với hai nguyên tắc hoạt động của robot) sau: Trang 2 + Dạng 1: G i j cho biết robot phải sơn cặp ghế (j, j+1) ở hàng ghế i; + Dạng 2: H i cho biết robot phải sơn các cặp ghế ở hai hàng i và i+1. + Các ký tự và số trên cùng dòng phải được ghi cách nhau bởi dấu cách. Ví dụ: BAI4.INP 4 4 BBBR BBBB WWWW WWWW BAI4.OUT 10 G 1 G 1 G 1 G 1 G 1 G 1 H 1 3 2 3 2 1 3  HẾT  Ghi chú : - Các tập tin bài làm phải đặt theo qui định BL1.PAS, BL2.PAS, BL3.PAS, BL4.PAS; - Đề thi có 03 trang; - Giám thị không giải thích gì thêm. Trang 3