Đề thi chọn đội tuyển chính thức tham dự kì thi chọn học sinh giỏi quốc gia năm 2014 môn Tin học - Sở GD&ĐT Ninh Bình (Có đáp án)

ĐỀ THI CHÍNH THỨC
SỞ GIÁO DỤC VÀ ĐÀO TẠO
NINH BÌNH
ĐỀ THI CHỌN ĐỘI TUYỂN CHÍNH THỨC
THAM DỰ KÌ THI CHỌN HSG QUỐC GIA NĂM 2014
MÔN: TIN HỌC
Ngày thi: 31/10/2013
 Thời gian làm bài 180 phút, không kể thời gian giao đề
(Đề thi gồm 04 câu, trong 03 trang)
Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian chạy
1 - Ghi đĩa
BLURAY.PAS
BLURAY.INP
BLURAY.OUT
1giây/test
2 - Khiêu vũ
DANCE.PAS
DANCE.INP
DANCE.OUT
1giây/test
3 - Đồng bạc cổ
MONEY.PAS
MONEY.INP
MONEY.OUT
1giây/test
4 - Vận chuyển
TRANSFORM.PAS
TRANSFORM.INP
TRANSFORM.OUT
1giây/test
Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. 
Bài 1: Ghi đĩa BLURAY (5 điểm)
Cho n file dữ liệu cần chép ra những chiếc đĩa Blu-ray DVD (loại đĩa DVD có dung lượng lớn hơn hàng chục lần đĩa DVD thường). Nếu biết cách sắp xếp các file ghi vào các đĩa một cách hợp lý thì sẽ tiết kiệm được nhiều đĩa hơn.
Yêu cầu: Cho biết dung lượng của mỗi đĩa Blu-ray DVD và kích thước các file, em hãy tìm một phương án sắp xếp các file vào mỗi đĩa Blu-ray DVD sao cho số đĩa cần sử dụng là ít nhất. Chú ý mỗi file chỉ nằm gọn trong một đĩa.
Dữ liệu vào: BLURAY.INP
Dòng 1: Ghi 2 số nguyên dương n và D. Trong đó n là số lượng file cần sao chép và D là dung lượng của mỗi đĩa Blu-ray DVD.
Dòng 2: Ghi n số nguyên dương a1, a2, an là kích thước của các file cần sao chép.
Dữ liệu ra: BLURAY.OUT
Ghi số đĩa Blu-ray DVD ít nhất cần dùng.
Giới hạn: n < 11; ai < D < 109 "i Î {1, 2, .. n}
Ví dụ:
BLURAY.INP
BLURAY.OUT
4 10
6 2 8 3
2
Giải thích: Cần 2 đĩa: 	Đĩa 1: 	6 + 3 = 9
Đĩa 2: 	2 + 8 = 10
Bài 2: Khiêu vũ (5 điểm)
	Một làng quê có m chàng trai đánh số từ 1 tới m và n cô gái đánh số từ 1 tới n. Chàng trai thứ i có chiều cao ai (i=1,2,,m), cô gái thứ j có chiều cao bj (j=1,2,,n). Trong một buổi khiêu vũ, người ta muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng 1 chàng trai và 1 cô gái và trong cặp đó chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong làng không được tham gia quá 1 cặp nhảy.
Yêu cầu: Tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.
Dữ liệu vào: chứa trong file DANCE.INP 
•	Dòng 1 chứa hai số nguyên dương m, n ≤105
•	Dòng 2 chứa m số nguyên dươnga1, a2,, am (ai≤109)
•	Dòng 3 chứa n số nguyên dương b1,b2,,bn (bj≤109)
Dữ liệu ra: Ghi ra file DANCE.OUT một số nguyên duy nhất là số cặp nhảy theo phương án tìm được.
Ví dụ:
DANCE.INP
DANCE.OUT
3 2
1 2 3
2 3
1
Chú ý: Ít nhất 50% số điểm ứng với các test có m, n ≤1000.
Bài 3: Đồng bạc cổ (5 điểm)
Mạng giao thông của quốc gia có n thành phố và m đường hai chiều, giữa hai thành phố có tối đa một đường hai chiều nối trực tiếp giữa chúng. Rôn là một chàng trai say mê sưu tầm tiền cổ và còn thiếu một đồng bạc đặc biệt thời trung cổ. Tra trên mạng Internet Rôn biết được danh sách k thành phố có bán đồng tiền này và giá bán ở mỗi thành phố này. Internet cũng cho biết chi phí dij đi từ i tới j nếu hai thành phố này có đường nối trực tiếp. Nhà Rôn nằm trên thành phố A, hôm nay Rôn về nhà thăm bố mẹ tại thành phố B, Rôn quyết định sẽ lái xe đi từ A tới B và sẽ mua đồng tiền cổ ở một trong số các thành phố trên đường đi. Vấn đề là phải chọn đường đi sao cho tổng chi phí đi từ A đến B cộng với chi phí mua đồng tiền cổ là nhỏ nhất.
Yêu cầu: Xác định tổng chi phí nhỏ nhất để thực hiện kế hoạch của Rôn.
Dữ liệu vào: Vào từ File MONEY.INP gồm:
• Dòng đầu tiên chứa 3 số nguyên n, m và k (2 ≤ n ≤ 5000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ n),
• Dòng thứ 2 chứa 2 số nguyên A và B,
• Dòng thứ 3 chứa k cặp số nguyên, mỗi cặp xác định thành phố và giá bán đồng tiền cổ (nằm trong phạm vi từ 1 đến 109), ở các thành phố khác nhau, giá khác nhau.
• Mỗi dòng trong m dòng còn lại chứa 3 số nguyên i, j và dij (1 ≤ dij ≤ 105).
Dữ liệu ra: Đưa ra File MONEY.OUT một số nguyên duy nhất là chi phí nhỏ nhất tìm được. Ghi chú: Có 60% số test có n ≤ 100
Ví dụ:
MONEY.INP
MONEY.OUT
5 7 4
1 4
1 100 4 50 3 10 2 55
1 2 10
5 3 42
1 3 30
2 4 50
3 4 70
2 5 24
4 5 21
103
Bài 4: Vận chuyển (5 điểm)
	Có n công trình cần vật liệu thi công. Công trường i cần cung cấp D[i] đơn vị hàng. Hàng được cung cấp từ hai kho A và B. Cước vận chuyển một đơn vị hàng từ kho A đến công trường i là A[i]. Cước vận chuyển một đơn vị hàng từ kho B đến công trường i là B[i]. Biết A có r đơn vị hàng và tổng số hàng của cả hai kho vừa đủ cung cấp cho n công trường.
Yêu cầu: Hãy phân phối hàng từ hai kho đến các công trường sao cho tổng cước phí vận chuyển là ít nhất.
Dữ liệu vào: cho trong file ‘TRANSFORM.INP’ gồm 4 dòng:
	+ Dòng 1: Chứa 2 số nguyên dương n và r	(0 < n, r < 103)	
+ Dòng 2: Chứa n số D[1] D[2] D[n]
	+ Dòng 3: Chứa n số A[1] A[2] A[n]	
+ Dòng 4: Chứa n số B[1] B[2] B[n]
Dữ liệu ra: Xuất ra file ‘TRANSFORM.OUT’ 
Ghi một số nguyên dương là tổng chi phí vận chuyển ít nhất.
Ví dụ: 
TRANSFORM.INP
TRANSFORM.OUT
Giải thích
5 100
30 80 80 50 40
3 5 10 4 23
4 6 2 7 4
1070
Hàng cung cấp lần lượt từ kho A và kho B cho 5 công trường là:
A: 30 20 0 50 0
B: 0 60 80 0 40
-----HẾT-----
Họ và tên thí sinh :................................................. Số báo danh ..........................
Họ và tên, chữ ký: Giám thị 1:...............................................................................
Họ và tên, chữ ký: Giám thị 2:................................................................................