Đề thi HSG Tin 9 huyện Lai Vung năm 2015-2016

PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN LAI VUNG KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2015 – 2016 ĐỀ CHÍNH THỨC MÔN THI: TIN HỌC Họ và tên thí sinh: .......................................... Chữ ký của giám thị 1: ...................... Thời gian làm bài: 150 phút Ngày thi: 17/01/2016 Số báo danh: .......................... Chữ ký của giám thị 2: ............................ NỘI DUNG ĐỀ THI (Đề thi có 02 trang, gồm 3bài) Hạn chế kỹ thuật: Thời gian thực hiện chương trình không quá 5 giây BÀI 1. (7 điểm) GIA CÔNG SẢN PHẦM Một cơ sở sản xuất hàng thủ công mỹ nghệ vừa nhận được một đơn đặt hàng gia công n sản phẩm. Với số lượng đặt hàng lớn như vậy, cơ sở đã huy động hết toàn bộ công nhân bắt tay vào làm ngay. Tuy nhiên đây lại là một sản phẩm mới nên ngày đầu tiên cơ sở chỉ làm ra được k sản phẩm. Sang ngày thứ hai, các công nhân đã thành thạo hơn nên số sản phẩm làm ra được nhiều gấp đôi ngày thứ nhất. Và cứ như vậy, năng suất của ngày hôm sau lại cao gấp đôi ngày hôm trước. Yêu cầu: Hãy cho biết cơ sở cần bao nhiêu ngày để hoàn thành hết n sản phẩm? Dữ liệu vào: Nhập từ bàn phím các số nguyên n, k (1≤n,k≤100000). Giả thiết dữ liệu được nhập đúng, không cần kiểm tra. Kết quả ra: Xuất ra màn hình số ngày hoàn thành các sản phẩm theo đơn đặt hàng. Ví dụ : Nhập từ bàn phím Số sản phẩm đặt hàng = 11 Số sản phẩm sản xuất trong ngày đầu tiên = 2 Xuất ra màn hình Số ngày hoàn thành = 3 Giải thích: - Ngày thứ nhất làm 2 sản phẩm (còn lại 9 sản phẩm). - Ngày thứ hai làm 4 sản phẩm (tổng cộng là 6, còn lại 5 sản phẩm). - Ngày thứ ba có thể làm được 8 sản phẩm nhưng chỉ làm 5 sản phẩm còn lại. BÀI 2. (6 điểm) DÃY KÝ TỰ SỐ Bạn Nam rất yêu thích lập trình, nhất là khi gặp những bài toán khó thì bạn ấy càng cố gắng để giải cho xong. Có một lần, trong lúc suy nghĩ về một bài toán, tay bạn ấy lại gõ ngẫu nhiên các phím trên bàn phím, đến khi nhìn lại thì trên màn hình đã là một dãy ký tự. Kỳ lạ thay, mặc dù là gõ ngẫu nhiên không nhìn bàn phím nhưng có những lúc bạn ấy chỉ toàn gõ vào các phím số. Yêu cầu: Cho xâu ký tự S là dãy các ký tự mà bạn Nam đã gõ vào, hãy cho biết bạn Nam đã gõ liên tiếp các phím số nhiều nhất là bao nhiêu lần? Dữ liệu vào: Cho từ tệp văn bản có tên BL2.INP gồm một dòng chứa xâu ký tự S (độ dài xâu không quá 250 ký tự). Kết quả: Ghi ra tệp văn bản có tên BL2.OUT có dạng: - Dòng đầu ghi số lần nhiều nhất mà bạn Nam gõ liên tiếp các phím số. - Nếu có ký tự số được gõ vào thì dòng thứ hai ghi dãy các số mà bạn nam gõ liên tiếp nhiều nhất đó. Nếu có nhiều dãy cùng có số lần gõ nhiều nhất như nhau thì in ra dãy đầu tiên. Ví dụ: BL2.INP azp572gkxt8906dqsh13dj BL2.OUT 4 8906 BÀI 3. (7 điểm) CHẠY TIẾP SỨC Trong kỳ thi hội khỏe phù đổng cấp huyện vừa qua có n vận động viên tham gia chạy ngắn, các vận động viên được đánh số báo danh từ 1 đến n. Kết quả thời gian chạy của vận động viên thứ i là t i (miligiây). Để chuẩn bị cho môn chạy tiếp sức trong kỳ thi hội khỏe phù đổng cấp tỉnh, ban huấn luyện muốn chọn ra 4 vận động viên chạy nhanh nhất trong số n vận động viên này. Yêu cầu: Hãy cho biết số báo danh của 4 vận động viên được chọn. Biết rằng không có hai vận động viên nào có cùng thành tích. Dữ liệu vào: Cho từ tệp văn bản có tên BL3.INP có dạng như sau: - Dòng đầu tiên ghi số nguyên n (4≤n≤1000) - n dòng tiếp theo, dòng thứ i ghi số nguyên dương ti là thời gian chạy của vận động viên thứ i ( ti ≤ 30000, i=1..n) Kết quả: Ghi ra tệp văn bản có tên BL3.OUT gồm một dòng ghi 4 số nguyên tương ứng là 4 số báo danh của 4 vận động viên được chọn (không cần ghi theo thứ tự). Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách. Ví dụ: BL3.INP 7 13000 9800 10200 11500 10060 12050 11200 BL3.OUT 2357 --- HẾT --Lưu ý: Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gì thêm. PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN LAI VUNG Hướng dẫn chấm gồm 03 trang HƯỚNG DẪN CHẤM VÀ THANG ĐIỂM KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2015 – 2016 MÔN: TIN HỌC BÀI 1. (7 điểm) GIA CÔNG SẢN PHẨM a. Thuật toán: Dùng cấu trúc lặp tăng dần để đếm số ngày b. Chương trình tham khảo: Program BL1; Var n,k,S,dem:Longint; Begin Write('So san pham dat hang = '); Readln(n); Write('So san pham san xuat trong ngay dau tien = '); Readln(k); S:=0; dem:=0; While S='0') and (S[i]<='9') then Begin dem:=dem+1; If dem>max then Begin max:=dem; vitri:=i; End ; End Else dem:=0; Assign(f,fout); ReWrite(f); Writeln(f,max); Write(f,Copy(S,vitri-max+1,max)); Close(f); End. c. Bộ TEST: TEST 1 Dữ liệu nhập sjdh25jsh00491sadjh2763smdajk 2 skldjl;a s';asdl'askasjdfajsj 3 sjdh;';7634re57834dfg57346gfh738947fkjash 12 3987ueirtjkdf,./l834782342907jshjlhk 834782342907 4 nb3478jdf348jgfh9038fgj348975dkj0-347dfg 9 83475jkfjk89-\=-aksdjh347jh000000000jksh 000000000 5 07304657018963457627456 6 Kết quả 5 00491 0 23 07304657018963457627456 hjhdf346576347895hjfgsdasdjklh8930247508 31 3740fghjdfhgjkdhfjk5389034750834750-812 123893745087234890573465874 ajkgjksdf12389374508723489057346587413 1367 67jhjk32762637ghsdgfsd7826789623457862 3478gsdgfhjsdggduyrtpy76789165789165018 6jhkjlasdggfhjasdgy576157645gfsgdfhlsgadfl 3478gwdhjsdhsa Điểm 0,5 0,5 1,0 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 BÀI 3. (7 điểm) CHẠY TIẾP SỨC a. Thuật toán: Sắp xếp dãy t theo thứ tự tăng dần và chọn 4 phần tử đầu. Lưu ý khi sắp xếp lưu lại số báo danh của vận động viên. b. Chương trình tham khảo: Program BL3; Const fin = 'BL31.INP'; fout= 'BL31.OUT'; Var t,sbd:Array[1..1000] of Integer; n,i,j,tam:Integer; f:Text; Begin Assign(f,fin); Reset(f); Readln(f,n); do Readln(f,t[i]); For i:=1 to n Close(f); to n do sbd[i]:=i; For i:=1 For i:=1 to 4 do do For j:=i+1 to n If t[i]>t[j] then Begin tam:=t[i]; t[i]:=t[j]; t[j]:=tam; tam:=sbd[i]; sbd[i]:=sbd[j]; sbd[j]:=tam; End; Assign(f,fout); ReWrite(f); do Write(f,sbd[i],' '); For i:=1 to 4 Close(f); End. c. Bộ TEST: Các dữ liệu nhập xem trong file BL3.INP TEST 1 2 3 4 5 6 7 File Input BL31.INP BL32.INP BL33.INP BL34.INP BL35.INP BL36.INP BL37.INP BL3.OUT 7101214 16 33 66 97 67 130 178 195 262 369 398 524 15 358 536 598 116 211 511 736 83 168 713 937 ---Hết--- Điểm 1,0 1,0 1,0 1,0 1,0 1,0 1,0