Đề thi chọn đội tuyển học sinh giỏi dự thi quốc gia môn Tin học - Năm học 2015-2016 - Sở GD&ĐT Ninh Bình

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN ĐỘI TUYỂN 
HỌC SINH GIỎI DỰ THI QUỐC GIA
Năm học 2015 – 2016
MÔN: Tin học
Ngày thi 29/10/2015
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 04 câu, trong 03 trang
Tên bài
Tên file chương trình
File dữ liệu vào
File kết quả ra
Bài 1
Biểu thức 
BAI1.PAS
BAI1.INP
BAI1.OUT
Bài 2
Du lịch Ninh Bình
BAI2.PAS
BAI2.INP
BAI2.OUT
Bài 3
Xóa số
BAI3.PAS
BAI3.INP
BAI3.OUT
Bài 4
Xe buýt
BAI4.PAS
BAI4.INP
BAI4.OUT
Bài 1 (2 điểm): Biểu thức
Trong biểu thức ((1?2)?3)?4)?5)?N) hãy thay các dấu ? bằng một trong bốn phép tính (+, -, *, /) sao cho giá trị của biểu thức đã cho bằng S. Gọi d là số lượng biểu thức tạo ra.
Yêu cầu: Xác định từng biểu thức tạo ra và số lượng các biểu thức tìm được.
Dữ liệu: 
Từ tệp văn bản BAI1.INP là 2 số nguyên dương N và S (1≤ N ≤ 20, 10-9 ≤ S ≤ 109).
Kết quả: Ghi ra file văn bản BAI1.OUT
	+ Nếu d = 0 thì dòng đầu tiên ghi số 0.
	+ Nếu d > 0 thì ghi số d tìm được.
Ví dụ: 
BAI1.INP
BAI1.OUT
5 1
6
Bài 2 (4 điểm): Du lịch Ninh Bình
Ninh Bình có hai tập đoàn kinh tế lớn Xuân Trường (gọi là Vàng) và Xuân Thành (gọi là Xanh) đều lập nghiệp từ ngành xây dựng. Nhưng do xu hướng phát triển của thời đại họ đã đầu tư vào lĩnh vực du lịch, có n điểm du lịch, đánh số từ 1 đến n (3 ≤ n ≤ 1000). Các điểm du lịch này được nối với nhau bởi hệ thống giao thông gồm m đường (n-1 ≤ m ≤ 5000), mỗi đường nối một cặp điểm du lịch và là đường 2 chiều, đảm bảo có đường đi lại giữa hai điểm du lịch bất kỳ (trực tiếp hoặc đi qua một số điểm du lịch khác). Giữa hai điểm du lịch bất kỳ có không quá một đường nối trực tiếp. Các điểm du lịch chi phối bởi tập đoàn Vàng được gọi là những điểm du lịch Vàng, các điểm du lịch còn lại bị chi phối bởi tập đoàn Xanh và được gọi là điểm du lịch Xanh. Một tua du lịch chỉ được thành lập giữa các điểm cùng màu. Khi tham gia tua khách hàng phải trả 1 đồng trên mỗi đường đi, ngoài ra, khi đi qua điểm du lịch khác màu với điểm du lịch xuất phát, khách hàng phải trả thêm 3 đồng. Dĩ nhiên, khách hàng bao giờ cũng chọn con đường ứng với giá tiền phải trả là nhỏ nhất.
Yêu cầu: Cho biết n, m và mạng giao thông giữa các điểm du lịch. Hãy tính thuế trung bình T phải trả khi tham gia tua du lịch giữa điểm cùng màu.
Dữ liệu: Vào từ file văn bản BAI2.INP:
- Dòng đầu tiên chứa 2 số nguyên n m,
- Dòng thứ 2 chứa xâu n ký tự, mỗi ký tự là Y hoặc G, ký tự thứ i xác định màu của thành phố i (i = 1 ¸ n),
- m dòng sau: mỗi dòng chứa 2 số nguyên i j xác định đường nối từ i tới j.
Kết quả: Đưa ra file văn bản BAI2.OUT số thực T với độ chính xác 10-9.
Ví dụ:
BAI2.INP
BAI2.OUT
5 5
YYGYG
1 2
5 1
3 4
3 2
5 4
4.00000000
Bài 3 (7 điểm): Xóa số
Cho một số tự nhiên a gồm n chữ số a = a1a2 ... an (aiÎ{0,1,2,3,4,5,6,7,8,9}; i=1,2...n). Hãy xoá bỏ m chữ số của a (vẫn giữ nguyên thứ tự của ai), sao cho số thu được sau khi xoá bỏ m chữ số đó là nhỏ nhất.
Yêu cầu: Xoá bỏ m chữ số của a, sao cho số thu được sau khi xoá bỏ m chữ số đó là nhỏ nhất.
Dữ liệu: Vào từ file văn bản BAI3.INP:
- Dòng 1 chứa 2 số nguyên dương m và n (1 ≤ m; n ≤ 106; m < n) cách nhau một dấu cách;
- Dòng thứ i trong n dòng tiếp theo chứa số ai (aiÎ{0,1,2,3,4,5,6,7,8,9}).
Kết quả: Đưa ra file văn bản BAI3.OUT gồm 1 dòng chứa số thu được sau khi xoá bỏ m chữ số đó là nhỏ nhất.
Ví dụ:
BAI3.INP
BAI3.OUT
2 5
6
1
4
2
7
127
Bài 4 (7 điểm): Xe buýt
Trên một tuyến đường ở thành phố du lịch X có các xe ô tô buýt công cộng phục vụ việc đi lại của du khách. Các bến xe buýt ở vị trí các cột cây số của tuyến đường. Trên hành trình, các xe buýt đều dừng lại tại các bến cho khách lên xuống. Mỗi bến đều có xe xuất phát, nhưng mỗi xe chỉ chạy không quá b km kể từ bến nó xuất phát. Hành khách khi đi xe sẽ phải trả tiền cho độ dài đoạn đường mà họ ngồi trên xe. Cước phí cần trả để đi đoạn đường độ dài i km là ci (i= 1, 2, ..., b) (cước phí chỉ phụ thuộc vào độ dài đoạn đường). Một du khách xuất phát từ một bến nào đó muốn đi dạo L km trên tuyến đường nói trên. Tính số tiền nhỏ nhất mà du khách phải trả cho chuyến dạo chơi bằng xe buýt.
Dữ liệu vào: Từ file văn bản BAI4.INP có cấu trúc:
	- Dòng 1 chứa hai số nguyên dương b, L (b ≤ 20; L ≤ 10000);
	- Dòng 2 chứa b số nguyên dương c1, c2, c3, , cb được ghi cách nhau bởi một dấu cách.
Dữ liệu ra: File văn bản BAI4.OUT gồm 1 dòng ghi tiền nhỏ nhất tìm được.
Ví dụ1:
BAI4.INP
BAI4.OUT
10 15
12 21 31 40 49 58 65 79 90 101
142 
Ví dụ2:
BAI4.INP
BAI4.OUT
10 10
20 30 28 41 50 60 70 70 91 101
97
------------------- HẾT -------------------
Họ và tên thí sinh :....................................................... Số báo danh ........................
Họ và tên, chữ ký: Giám thị 1:...................................................................................
Giám thị 2:...........................................................................