Kì thi chọn học sinh giỏi lớp 9 năm học 2015 - 2016 đề thi môn: Tin học thời gian: 150 phút, không kể thời gian giao đề

SỞ GD&ĐT VĨNH PHÚC 
KÌ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2015-2016 
ĐỀ THI MÔN: TIN HỌC 
Thời gian: 150 phút, không kể thời gian giao đề 
(Đề thi có 02 trang) 
Tổng quan về đề thi 
Tên bài Chương trình Dữ liệu Kết quả Thời gian Bộ nhớ 
Mua sữa buymilk.* buymilk.inp buymilk.out 1 giây 256Mb 
Tạo chuỗi makestr.* makestr.inp makestr.out 1 giây 256Mb 
Tổng tích prodsum.* prodsum.inp prodsum.out 1 giây 256Mb 
Chú ý: thí sinh thay * trong File chương trình là CPP hoặc PAS tùy theo ngôn ngữ lập trình mà thí 
sinh sử dụng là C++ hoặc Pascal. 
Lập chương trình giải các bài toán sau đây 
Bài 1. Mua sữa [buymilk] 
Ngân sách dành cho mua sữa của gia đình Bờm là 
 đồng, Bờm là người chịu trách nhiệm quản 
lý chi tiêu hạng mục này. Ở đại lý, có hai hình thức đóng gói: sữa đựng trong hộp giấy 1 lít có 
giá  đồng; sữa đựng trong chai thủy tinh 1 lít có giá  đồng. Siêu thị đang có chương trình 
thu mua vỏ chai sữa thủy tinh với giá  đồng một vỏ chai. Bờm có thể bán lại vỏ chai thủy tinh 
để giảm chi phí. 
Hãy xác định số lít sữa nhiều nhất mà Bờm có thể mua được cho gia đình với ngân sách ban 
đầu 
. 
Dữ liệu 
• Dòng 1: bốn số nguyên 
, , ,  ngăn cách nhau bởi dấu cách. 
Kết quả 
• Dòng 1: số nguyên là số lít sữa tối đa Bờm có thể mua được. 
Ví dụ 
buymilk.inp buymilk.out Giải thích 
20 3 10 8 8 Bờm sẽ thực hiện 6 lần mua sữa đóng chai 
và 2 lần mua sữa đựng trong hộp giấy 
Giới hạn 
• 1 ≤ 
, ≤ 10	
, 1 ≤  <  ≤ 10	
Bài 2. Tạo chuỗi [makestr] 
Chỉ sử dụng  kí tự đầu tiên trong bảng chữ cái Latin hãy xây dựng xâu dài nhất thỏa mãn 
đồng thời các điều kiện sau: 
• Ký tự thứ 
 xuất hiện trong xâu không quá  lần; 
• Các ký tự xuất hiện trong xâu có số lần xuất hiện đôi một phân biệt. 
Dữ liệu 
• Dòng 1: số nguyên ; 
ĐỀ CHÍNH THỨC 
• Dòng 2:  số nguyên 	, ,  , , trong đó  là giới hạn số lần xuất hiện trong xâu của 
kí tự thứ 
 (trong bảng chữ cái), các số cách nhau ít nhất một dấu cách. 
Kết quả 
• Dòng 1: số nguyên là độ dài lớn nhất của xâu tìm được. 
Ví dụ 
makestr.inp makestr.out Giải thích 
3 
1 1 2 
3 Xâu có thể là: “cbc” hoặc “acc”... 
Giới hạn 
• 2 ≤  ≤ 26; 
• 1 ≤  ≤ 10. 
Bài 3: Tổng tích [prodsum] 
Cho dãy số nguyên  phần tử 
 = (	, ,  , ). Trọng số  của 
 được tính như sau: 
 =
 × 

	
Chẳng hạn, với 
 = (4, 3, 2, 5), trọng số của 
 là  = 1 × 4 + 2 × 3 + 3 × 2 + 4 × 5 = 36. 
Được phép thực hiện một lần biến đổi trên 
 là: di chuyển một phần tử nào đó tới vị trí đầu 
hoặc cuối dãy. Tìm trọng số  lớn nhất có thể của dãy thu được. 
Dữ liệu 
• Dòng 1: số nguyên ; 
• Dòng 2:  số nguyên		, ,  ,  cách nhau ít nhất bởi một dấu cách. 
Kết quả 
• Dòng 1: số nguyên là trọng số  lớn nhất thu được. 
Ví dụ 
prodsum.inp prodsum.out Giải thích 
4 
4 3 2 5 
39 Chuyển phần tử thứ 3 (2) về đầu, được dãy: 2 4 3 5 
Dãy này có trọng số 
 = 1 × 2 + 2 × 4 + 3 × 3 + 4 × 5 = 39 
4 
1 2 3 4 
30 Dãy ban đầu đã có trọng số lớn nhất có thể 
Giới hạn 
• 2 ≤  ≤ 200000; 
• || ≤ 10#	∀
 = 1 ÷ . 
--------------- 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: .................................................................................................... Số báo danh: ....................................................