Đề thi chọn HSG cấp tỉnh lớp 12 THPT môn Tin học năm 2016-2017 (Vòng 2)

SỞ GIÁO DỤC VÀ ĐÀO TẠO<br /> <br /> KỲ THI CHỌN HỌC SINH GIỎI TỈNH THPT<br /> NĂM HỌC 2016-2017<br /> Môn: Tin học<br /> Thời gian: 180 phút (Không kể thời gian giao đề)<br /> Ngày thi thứ hai: 29/10/2016<br /> <br /> ĐỀ THI CHÍNH THỨC<br /> (Đề thi gồm có 03 trang)<br /> <br /> TỔNG QUAN BÀI THI<br /> Bài<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> <br /> Tên bài<br /> Giá trị của đa thức<br /> Số nguyên lớn nhất<br /> Biến đổi bảng số<br /> Lập lịch phòng hội thảo<br /> Xây dựng ống dẫn nước<br /> <br /> Tên chương trình<br /> DATHUC.PAS<br /> SNLN.PAS<br /> BANGSO.PAS<br /> LICH.PAS<br /> BUILD.PAS<br /> <br /> File dữ liệu vào<br /> DATHUC.INP<br /> SNLN.INP<br /> BANGSO.INP<br /> LICH.INP<br /> BUILD.INP<br /> <br /> File kết quả<br /> DATHUC.OUT<br /> SNLN.OUT<br /> BANGSO.OUT<br /> LICH.OUT<br /> BUILD.OUT<br /> <br /> Bài 1 (4,0 điểm). Giá trị của đa thức<br /> Cho đa thức sau: a0 + a1.x1 + a2.x2 + a3.x3 + … + an.xn.<br /> Tính giá trị của đa thức đã cho.<br /> Dữ liệu vào: Cho trong tệp văn bản DATHUC.INP gồm 2 dòng:<br /> -<br /> <br /> Dòng 1: Gồm số nguyên n (0  n  100) và số thực x (–1000  x  1000)<br /> <br /> -<br /> <br /> Dòng 2: Chứa n +1 số thực theo thứ tự tương ứng với a0, a1 a2 a3 … an<br /> (mỗi số cách nhau ít nhất một khoảng trắng).<br /> <br /> Dữ liệu ra: Ghi ra tệp DATHUC.OUT gồm duy nhất một số thực là giá trị đa thức<br /> tìm được (làm tròn 2 chữ số sau hàng thập phân).<br /> Ví dụ:<br /> DATHUC.INP<br /> <br /> DATHUC.OUT<br /> <br /> 3 2.0<br /> <br /> 14.50<br /> <br /> 5.5 2.5 3.0 –1.0<br /> Bài 2 (4,0 điểm). Số nguyên lớn nhất<br /> Nguyên và Sơn đều rất thích các trò chơi với những con số. Hai bạn thường nghĩ ra<br /> các câu đố vui để thử tài với nhau. Hôm nay, Nguyên đưa ra cho Sơn một câu đố vui như sau:<br /> Cho Sơn trước số nguyên X (1  X  1025). Sơn hãy tìm số nguyên lớn nhất nhưng nhỏ hơn<br /> X và có cùng các chữ số với X. Câu đố này làm Sơn tìm khá lâu. Các bạn hãy lập trình giúp<br /> Sơn tìm nhanh số nguyên lớn nhất thỏa yêu cầu của Nguyên?<br /> Dữ liệu vào: Từ tệp văn bản SNLN.INP gồm một dòng duy nhất chứa số X.<br /> Dữ liệu ra: Ghi ra tệp văn bản SNLN.OUT gồm một dòng ghi số tìm được, nếu<br /> không tồn tại ghi số 0.<br /> Ví dụ:<br /> SNLN.INP<br /> 342<br /> <br /> SNLN.OUT<br /> 324<br /> <br /> SNLN.INP<br /> 567<br /> <br /> SNLN.OUT<br /> 0<br /> <br /> Trang 1/3<br /> <br /> Bài 3 (4,0 điểm). Biến đổi bảng số<br /> Cho ma trận số nguyên cấp NxN (các phần tử kề nhau trong cùng một hàng, một cột<br /> khác nhau).<br /> Yêu cầu: Tìm cách đổi chỗ các phần tử trong ma trận để thu được một ma trận mới có<br /> tính chất sau: tổng các phần tử trên mỗi dòng, mỗi cột bằng nhau.<br /> Dữ liệu vào: Từ tệp văn bản BANGSO.INP<br /> - Dòng đầu tiên chứa số N, (3 ≤ N ≤ 100).<br /> - N dòng tiếp theo mỗi dòng chứa N số nguyên. Mỗi số cách nhau một khoảng<br /> trắng.<br /> Dữ liệu ra: Ghi vào tệp văn bản BANGSO.INP<br /> - Nếu có thể biến đổi được thì ghi ra dòng đầu tiên của file tổng các phần tử<br /> trên một dòng bất kỳ trong ma trận thu được.<br /> - Nếu không biến đổi được thì ghi ra dòng đầu tiên của file số 0.<br /> Ví dụ:<br /> BANGSO.INP<br /> 5<br /> 12345<br /> 6 7 8 9 10<br /> 11 12 13 14 15<br /> 16 17 18 19 20<br /> 21 22 23 24 25<br /> <br /> BANGSO.OUT<br /> 65<br /> <br /> Bài 4 (4,0 điểm). Lập lịch phòng hội thảo<br /> Có N cuộc họp được đánh số từ 1 đến N đăng ký làm việc tại một phòng hội thảo. Cuộc<br /> họp i cần được bắt đầu tại thời điểm Ai và kết thúc tại thời điểm Bi (i=1,2,...N). Hai cuộc họp<br /> bất kỳ chỉ được nhận phục vụ nếu các khoảng thời gian làm việc tương ứng chỉ có thể được<br /> giao nhau tại đầu mút. Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ được nhiều<br /> cuộc họp nhất.<br /> Dữ liệu vào: Từ tệp văn bản LICH.INP có cấu trúc như sau:<br /> -<br /> <br /> Dòng đầu tiên chứa số nguyên dương N (1≤N≤50).<br /> <br /> -<br /> <br /> Dòng thứ i trong số N dòng tiếp ghi 2 số nguyên Ai và Bi.<br /> <br /> Dữ liệu ra: Ghi ra tệp văn bản LICH.OUT có cấu trúc như sau:<br /> -<br /> <br /> Dòng 1 ghi giá trị K là số cuộc họp tối đa có thể bố trí được.<br /> <br /> -<br /> <br /> Dòng 2 ghi số hiệu của các cuộc họp được phục vụ theo trình tự lịch bố trí.<br /> <br /> Lưu ý: Các giá trị trên cùng một dòng cách nhau bởi khoảng trắng..<br /> Ví dụ:<br /> LICH.INP<br /> 5<br /> 1<br /> 2<br /> 1<br /> 3<br /> 7<br /> <br /> 3<br /> 4<br /> 6<br /> 5<br /> 9<br /> <br /> LICH.OUT<br /> 3<br /> 1 4 5<br /> <br /> Trang 2/3<br /> <br /> Bài 5 (4,0 điểm). Xây dựng ống dẫn nước.<br /> Ông Hai muốn xây dựng một hệ thống để dẫn nước đến N thửa ruộng trong trang trại<br /> của mình.<br /> Thửa ruộng thứ i được mô tả bởi một điểm (Xi, Yi) trong không gian hai chiều và không<br /> có hai thửa ruộng nào có cùng tọa độ. Chi phí để xây dựng một đường ống nước giữa hai thửa<br /> ruộng i và j phụ thuộc vào khoảng cách giữa chúng.<br /> Để xây dựng hệ thống đường ống với chi phí là thấp nhất có thể mà vẫn đảm bảo tất cả<br /> các thửa ruộng trong trang trại đều được có đường ống dẫn tới, để nước từ một đường ống bất<br /> kì có thể thông qua hệ thống ống dẫn tới một thửa ruộng khác.<br /> Ông Hai chỉ đồng ý lắp đặt nếu khảo sát chi phí đó nhỏ hơn C.<br /> Yêu cầu: Hãy lập trình tìm số tiền tối thiểu mà ông Hai sẽ phải trả để xây dựng hệ thống<br /> như trên.<br /> Dữ liệu vào: file BUILD.INP gồm:<br /> -<br /> <br /> Dòng 1: chứa hai số nguyên N và C, (1 ≤ N ≤ 2000; 1 ≤ C ≤ 106).<br /> <br /> - N dòng tiếp theo, dòng thứ i mô tả thửa ruộng thứ i với tọa độ (xi, yi). (0 ≤ xi ≤<br /> 1000, 0 ≤ yi ≤ 1000).<br /> Kết quả ra: file BUILD.OUT ghi ra chi phí tối thiểu để xây dựng đường ống, hoặc ghi<br /> ra – 1 nếu không thể xây dựng được.<br /> Ví dụ:<br /> BUILD.INP<br /> <br /> BUILD.OUT<br /> <br /> 3 11<br /> <br /> 46<br /> <br /> 02<br /> 50<br /> 43<br /> <br /> ………………………… Hết ………………………….<br /> Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.<br /> <br /> Họ và tên thí sinh ……………………………………...… Số báo danh ………… Phòng thi<br /> ……..<br /> Cán bộ coi thi thứ nhất ………………………… Cán bộ coi thi thứ hai<br /> …………………………...<br /> <br /> Trang 3/3<br /> <br />