Đề thi chọn học sinh giỏi khối 9 - Môn thi: Tin

Nội dung text: Đề thi chọn học sinh giỏi khối 9 - Môn thi: Tin

1. UBND HUYỆN LAI VUNG KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 PHÒNG GIÁO DỤC VÀ ĐÀO TẠO NĂM HỌC 2014 – 2015 ĐỀ CHÍNH THỨC MÔN THI: TIN HỌC (Đề thi gồm 03 trang) Thời gian: 150 phút (không kể thời gian giao đề) Ngày thi: 07/12/2014 Tổng quan đề thi: Bài Tên tệp chương trình Dữ liệu vào Kết quả ra Bài 1 BL1.PAS Nhập từ bàn phím Xuất ra màn hình Bài 2 BL2.PAS Nhập từ bàn phím Xuất ra màn hình Bài 3 BL3.PAS BL3.INP BL3.OUT Bài 4 BL4.PAS BL4.INP BL4.OUT 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. (5,0 điểm) NHỮNG ĐÓA HOA HỒNG Tôn sư trọng đạo là một truyền thống văn hoá vô cùng tốt đẹp của dân tộc ta. Để tỏ lòng tri ân đến quý thầy cô nhân ngày nhà giáo Việt Nam, các bạn học sinh lớp 9A dự định sẽ mua những cành hoa hồng đẹp nhất để tặng cho tất cả thầy cô trong toàn trường. Theo tìm hiểu của bạn lớp trưởng thì nhà trường có n thầy cô giáo, do đó các bạn cần mua n cành hoa hồng. Tại cửa hàng bán hoa, giá của mỗi cành hoa hồng là m đồng. Tuy nhiên, cửa hàng có chính sách giảm giá nếu khách hàng mua từ a cành hoa hồng trở lên thì giá bán sẽ giảm 25%. Yêu cầu: Hãy tính tổng số tiền mà các bạn lớp 9A cần có để mua đủ số cành hoa hồng như dự định. Dữ liệu vào: Nhập từ bàn phím các giá trị n, m, a (n, m, a là các số nguyên, 1≤n≤100, 1000≤m≤10000, 5≤a≤50). 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ố tiền cần có. Kết quả làm tròn đến phần nguyên. Ví dụ 1: Nhập từ bàn phím Xuất ra màn hình Số hoa cần mua = 15 Số tiền cần có = 15000 Đơn giá một cành hoa hồng = 1000 Số hoa tối thiểu để được giảm giá = 20 Ví dụ 2: Nhập từ bàn phím Xuất ra màn hình Số hoa cần mua = 30 Số tiền cần có = 22500 Đơn giá một cành hoa hồng = 1000 Số hoa tối thiểu để được giảm giá = 10 Giải thích: giá mỗi hoa là 1000 đồng, nhưng mua số lượng nhiều hơn 10 hoa được giảm 25% nên giá mỗi hoa giảm còn 750 đồng Trang 1/7
2. BÀI 2. (5,0 điểm) CHIA QUÀ Trong ngày Tết Trung thu, nhà thiếu nhi đã tổ chức rước đèn trung thu cho các em thiếu thi. Tất cả các em đều hào hứng tham gia các trò chơi của ban tổ chức. Để động viên tinh thần các em, ban tổ chức sẽ chấm điểm ở các trò chơi để xếp hạng và phát quà. Tuy nhiên vì là ngày vui, ban tổ chức muốn tất cả các em đều nhận được quà, kể cả em xếp hạng cuối cùng. Cách phát quà của ban tổ chức như sau: em xếp hạng cuối cùng sẽ được 1 gói quà, em xếp hạng kế trên em cuối cùng được 4 gói quà, Nói chung, em xếp hạng cao sẽ có số gói quà nhiều hơn bạn xếp hạng liền sau mình 3 gói quà. Biết rằng có n em tham gia rước đèn trung thu và khi tổng kết điểm thì không có hai em nào có cùng số điểm. Yêu cầu: Hãy cho biết ban tổ chức cần chuẩn bị bao nhiêu gói quà để phát trong đêm Trung thu nếu số lượng em thiếu nhi tham gia đã được biết trước? Dữ liệu vào: Nhập từ bàn phím số nguyên dương n là số em thiếu nhi tham gia rước đèn trung thu (1≤n≤1000). Kết quả ra: Xuất ra màn hình số gói quà mà ban tổ chức cần chuẩn bị. Ví dụ: Nhập từ bàn phím Xuất ra màn hình Số em thiếu nhi = 5 Số gói quà chuẩn bị = 35 Giải thích: Số quà từng em nhận được lần lượt là: 1, 4, 7, 10, 13 BÀI 3. (5,0 điểm) CHUỖI NGỌC Dọc theo con đường tơ lụa, những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của Phương Đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên (1 ≤ n ≤ 250). Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (ai, bi), tức là phải có ngọc loại ai đi trước loại bi (i = 1 k, 1 ≤ k ≤ 676). Nếu giá trị chuỗi ngọc đủ lớn, lãnh chúa sẽ mua toàn bộ chuỗi ngọc. Yêu cầu: Cho biết số viên ngọc n, xâu S thể hiện các loại ngọc trong chuỗi và cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc. 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 hai số nguyên n và k. - Dòng thứ hai chứa xâu S. - Tiếp theo là k dòng, mỗi dòng chứa hai ký tự xác định cặp giá trị. Kết quả: Ghi ra tệp văn bản có tên BL3.OUT gồm một số nguyên duy nhất là giá trị của chuỗi ngọc. Trang 2/7
3. Ví dụ: a b a c a b a BL3.INP BL3.OUT 7 3 7 abacaba a b a c a b a ab ac a b a c a b a bb Giải thích: - Dòng thứ ba là cách thứ nhất xác định cặp giá trị: ngọc loại a đứng trước ngọc loại b. Với cách này thì có 4 cặp (xem hình bên). - Dòng thứ tư là cách thứ hai xác định cặp giá trị: ngọc loại a đứng trước ngọc loại c. Với cách này thì có 2 cặp. - Dòng thứ năm là cách thứ ba xác định cặp giá trị: ngọc loại b đứng trước ngọc loại b. Với cách này thì có 1 cặp. BÀI 4. (5,0 điểm) TỔNG LỚN NHẤT Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên bảng, Nam viết số thứ nhất, Bình viết số thứ hai, rồi đến lượt Nam viết số thứ ba, Cứ tiếp tục như vậy hai bạn viết được một dãy gồm n số a1, a2, , an . Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẳn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất. Vì dãy số có quá nhiều số nên cả lớp nhìn hoa cả mắt mà vẫn chưa tìm ra được đáp án. Bạn hãy lập trình giải giúp các bạn trong lớp nhé. Dữ liệu vào: Cho từ tệp văn bản có tên BL4.INP có dạng như sau: - Dòng đầu tiên ghi số nguyên n (1≤n≤1000) - Dòng thứ hai ghi dãy n số nguyên a1, a2, , an (-1000 ≤ ai ≤ 1000, i=1 n) Kết quả: Ghi ra tệp văn bản có tên BL4.OUT gồm một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy. Ví dụ: BL4.INP BL4.OUT 10 15 2 -9 4 1 -3 5 8 -7 3 1 HẾT Họ và tên thí sinh: Số báo danh: Chữ ký của giám thị 1: Chữ ký của giám thị 2: 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. Trang 3/7
4. PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HƯỚNG DẪN CHẤM VÀ THANG ĐIỂM HUYỆN LAI VUNG KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2014 – 2015 MÔN: TIN HỌC BÀI 1. (5 điểm) NHỮNG ĐÓA HOA HỒNG a. Thuật toán: Kiểm tra nếu số hoa cần mua nhỏ hơn số hoa tối thiểu để được giảm giá thì số tiền = số hoa * đơn giá; ngược lại thì số tiền = số hoa * đơn giá * 0.75 b. Chương trình tham khảo: Program BL1; Var n,m,a:Longint; Begin Write('So hoa can mua = '); Readln(n); Write('Don gia mot canh hoa = '); Readln(m); Write('So hoa toi thieu de duoc giam gia = '); Readln(a); If n<a then Write('So tien can co = ',n*m) Else Write('So tien can co = ',n*m*0.75 :8:0); Readln; End. c. Bộ TEST: TEST Dữ liệu nhập Kết quả Điểm 1 n = 20 100000 1,0 m = 5000 a = 30 2 n = 25 30000 1,0 m = 1200 a = 50 3 n = 15 20250 1,0 m = 1800 a = 5 4 n = 27 24300 1,0 m = 1200 a = 27 5 n = 100 750000 1,0 m = 10000 a = 30 Trang 4/7
5. BÀI 2. (5 điểm) CHIA QUÀ a. Thuật toán: Đây là bài toán tính tổng n phần tử đầu tiên của cấp số cộng có công sai d=3. Cũng có thể áp dụng lệnh For để tính. b. Chương trình tham khảo: Program BL2; Var n,i,a,S:Longint; Begin Write('So em thieu nhi = '); Readln(n); S:=1; a:=1; For i:=2 to n do Begin a:=a+3; S:=S+a; End; Write('So goi qua chuan bi = ',S); Readln; End. c. Bộ TEST: TEST Dữ liệu nhập Kết quả Điểm 1 10 145 1,0 2 245 89915 1,0 3 679 691222 1,0 4 853 1090987 1,0 5 1000 1499500 1,0 BÀI 3. (5 điểm) CHUỖI NGỌC a. Thuật toán: Với mỗi cặp vị trí i và j (i<j) trong xâu chuỗi, ta kiểm tra xem cặp ký tự Si, Sj có nằm trong số k cặp giá trị hay không. Để giảm thời gian kiểm tra, ta dùng một mảng hai chiều A[‘a’ ’z’, ‘a’ ’z’] để đánh dấu các cặp giá trị. b. Chương trình tham khảo: Program BL3; Const fin ='BL3.INP'; fout='BL3.OUT'; Var A:Array['a' 'z','a' 'z'] of Integer; S:String; c1,c2:Char; n,k,i,j,d:Longint; f:Text; Begin Assign(f,fin); Reset(f); Readln(f,n,k); Readln(f,S); Trang 5/7
6. For i:=1 to k do Begin Readln(f,c1,c2); A[c1,c2]:=1; End; Close(f); n:=Length(S); d:=0; For i:=1 to n-1 do For j:=i+1 to n do d:=d + A[s[i],s[j]]; Assign(f,fout); ReWrite(f); Write(f,d); Close(f); End. c. Bộ TEST: Các dữ liệu nhập xem trong file BL31.INP TEST File Input BL3.OUT Điểm 1 BL31.INP 13 1,0 2 BL32.INP 52 1,0 3 BL33.INP 159 1,0 4 BL34.INP 1730 1,0 5 BL35.INP 13785 1,0 BÀI 4. (5 điểm) TỔNG LỚN NHẤT a. Thuật toán: Mỗi đoạn con được xác định bởi vị trí phần tử bắt đầu đoạn và vị trí phần tử cuối đoạn. Với mỗi đoạn con, ta tính tổng các phần tử của đoạn rồi so sánh chọn ra tổng lớn nhất. Gọi Sk = a1 + a2 + ak (k=1 n) Khi đó ta có ai + ai+1 + + aj = Sj – Si-1 (ở đây ta khởi tạo S0=0) Theo cách này ta không cần lưu lại mảng a. b. Chương trình tham khảo: Program BL4; Const fin ='BL4.INP'; fout='BL4.OUT'; Var S:Array[0 1000] of Longint; n,x,i,j,max:Longint; f:Text; Begin Assign(f,fin); Reset(f); Readln(f,n); S[0]:=0; For i:=1 to n do Begin Read(f,x); S[i]:=S[i-1] + x; End; Close(f); Trang 6/7
7. max:=S[1]; For i:=1 to n do For j:=i to n do If max < S[j]-S[i-1] then max:=S[j] - S[i-1]; Assign(f,fout); ReWrite(f); Write(f,max); Close(f); End. c. Bộ TEST: Các dữ liệu nhập xem trong file TEST File Input BL4.OUT Điểm 1 BL41.INP 9 1,0 2 BL42.INP 909 1,0 3 BL43.INP 2327 1,0 4 BL44.INP 3523 1,0 5 BL45.INP 7893 1,0 Hết Trang 7/7