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

Sau đây là Đề thi chọn HSG cấp tỉnh lớp 12 THPT môn Tin học năm 2016-2017 (Vòng 2) giúp các bạn học sinh tự đối chiếu, đánh giá sau khi thử sức mình với đề thi học sinh giỏi. Cùng tham khảo nhé.
Nội dung trích xuất từ tài liệu:
Đề 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ẠOKỲ THI CHỌN HỌC SINH GIỎI TỈNH THPTNĂM HỌC 2016-2017Môn: Tin họcThời gian: 180 phút (Không kể thời gian giao đề)Ngày thi thứ hai: 29/10/2016ĐỀ THI CHÍNH THỨC(Đề thi gồm có 03 trang)TỔNG QUAN BÀI THIBài1.2.3.4.5.Tên bàiGiá trị của đa thứcSố nguyên lớn nhấtBiến đổi bảng sốLập lịch phòng hội thảoXây dựng ống dẫn nướcTên chương trìnhDATHUC.PASSNLN.PASBANGSO.PASLICH.PASBUILD.PASFile dữ liệu vàoDATHUC.INPSNLN.INPBANGSO.INPLICH.INPBUILD.INPFile kết quảDATHUC.OUTSNLN.OUTBANGSO.OUTLICH.OUTBUILD.OUTBài 1 (4,0 điểm). Giá trị của đa thứcCho đa thức sau: a0 + a1.x1 + a2.x2 + a3.x3 + … + an.xn.Tính giá trị của đa thức đã cho.Dữ liệu vào: Cho trong tệp văn bản DATHUC.INP gồm 2 dòng:-Dòng 1: Gồm số nguyên n (0  n  100) và số thực x (–1000  x  1000)-Dòng 2: Chứa n +1 số thực theo thứ tự tương ứng với a0, a1 a2 a3 … an(mỗi số cách nhau ít nhất một khoảng trắng).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ứctìm được (làm tròn 2 chữ số sau hàng thập phân).Ví dụ:DATHUC.INPDATHUC.OUT3 2.014.505.5 2.5 3.0 –1.0Bài 2 (4,0 điểm). Số nguyên lớn nhấtNguyê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ĩ racá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: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ơnX 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úpSơn tìm nhanh số nguyên lớn nhất thỏa yêu cầu của Nguyên?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.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ếukhông tồn tại ghi số 0.Ví dụ:SNLN.INP342SNLN.OUT324SNLN.INP567SNLN.OUT0Trang 1/3Bài 3 (4,0 điểm). Biến đổi bảng số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ộtkhác nhau).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ó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.Dữ liệu vào: Từ tệp văn bản BANGSO.INP- Dòng đầu tiên chứa số N, (3 ≤ N ≤ 100).- 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ảngtrắng.Dữ liệu ra: Ghi vào tệp văn bản BANGSO.INP- 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ửtrên một dòng bất kỳ trong ma trận thu được.- Nếu không biến đổi được thì ghi ra dòng đầu tiên của file số 0.Ví dụ:BANGSO.INP5123456 7 8 9 1011 12 13 14 1516 17 18 19 2021 22 23 24 25BANGSO.OUT65Bài 4 (4,0 điểm). Lập lịch phòng hội thảoCó 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ộchọ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ọpbấ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ể đượcgiao 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ềucuộc họp nhất.Dữ liệu vào: Từ tệp văn bản LICH.INP có cấu trúc như sau:-Dòng đầu tiên chứa số nguyên dương N (1≤N≤50).-Dòng thứ i trong số N dòng tiếp ghi 2 số nguyên Ai và Bi.Dữ liệu ra: Ghi ra tệp văn bản LICH.OUT có cấu trúc như sau:-Dòng 1 ghi giá trị K là số cuộc họp tối đa có thể bố trí được.-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í.Lưu ý: Các giá trị trên cùng một dòng cách nhau bởi khoảng trắng..Ví dụ:LICH.INP51213734659LICH.OUT31 4 5Trang 2/3Bài 5 (4,0 điểm). Xây dựng ống dẫn nước.Ô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ạicủa mình.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ôngcó 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ửaruộng i và j phụ thuộc vào khoảng cách giữa chúng.Để 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ả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ấtkì có thể thông qua hệ thống ống dẫn tới một thửa ruộng khác.Ông Hai chỉ đồng ý lắp đặt nếu khảo sát chi phí đó nhỏ hơn C.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ốngnhư trên.Dữ liệu vào: file BUILD.INP gồm:-Dòng 1: chứa hai số nguyên N và C, (1 ≤ N ≤ 2000; 1 ≤ C ≤ 106).- 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 ≤1000, 0 ≤ yi ≤ 1000).Kết quả ra: file BUILD.OUT ghi ra chi phí tối thiểu để xây dựng đường ống, hoặc ghira – 1 nếu không thể xây dựng được.Ví dụ:BUILD.INPBUILD.OUT3 1146025043………………………… Hết ………………………….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.Họ và tên thí sinh ……………………………………...… Số báo danh ………… Phòng thi……..Cán bộ coi thi thứ nhất ………………………… Cán bộ coi thi thứ hai…… ...