SỞ GIÁO DỤC-ĐÀO TẠO KÌ THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI
THÀNH PHỐ ĐÀ NẴNG LỚP 12 THPT - NĂM HỌC 2010-2011
Môn: TIN HỌC
Thời gian: 180 phút (không tính thời gian giao đề)
ĐỀ CHÍNH THỨC VÒNG 2

Chú ý: Bài thi gồm có 3 bài trong 3 trang
Tổng quan đề thi KHỐI LẬP PHƯƠNG BÁN LỢN CHỌN KẸO
Tên bài làm BL1.PAS BL2.PAS BL3.PAS
Dữ liệu vào BLOCK.INP PIGS.INP SWE.INP
Dữ liệu ra BLOCK.OUT PIGS.OUT SWE.OUT
CÂU 1. KHỐI LẬP PHƯƠNG
Có N (1≤ N ≤ 200) khối lập phương, mỗi khối có một trong ba màu: Vàng, Bạc,
Đồng. Các khối được xếp liên tiếp nhau tạo thành một dãy. Dãy các khối cùng màu liên
tiếp nhau tạo thành một khoang. Số lượng khối trong mỗi khoang được gọi là độ dài của
khoang.

Ví dụ ở hình 1, ta có 4 khoang với độ dài 1, 4, 3, 1.
Ở mỗi thời điểm ta có thể chọn một khoang bất kỳ, lấy tất cả các khối của khoang
ra khỏi dãy và dồn các khối còn lại cho sít nhau.
Nếu khoang có độ dài K, ta sẽ nhận được điểm là K
2
. Số điểm ban đầu là 0.
Ví dụ, nếu chọn khoang bạc ta sẽ được 4
2
= 16 điểm. Ta có thể chọn nhiều lần cho
đến khi dãy trở nên rỗng. Tổng số điểm phụ thuộc vào trình tự chọn.
Một cách chọn:
⇒ ⇒ ⇒ Rỗng

Điểm = 0 Điểm = 16 Điểm = 25 Điểm = 29

Dữ liệu ra: Đưa ra file văn bản BLOCK.OUT có cấu trúc như sau:
• Kết quả của mỗi test đưa ra trên một dòng và có dạng:
# Số thứ tự của Test : Tổng điểm
Ví dụ:
BLOCK.INP BLOCK.OUT
2
9
1 2 2 2 2 3 3 3 1
1
1
#1: 29
#2: 1
CÂU 2. BÁN LỢN
Bác John sống ở trang trại tại thị trấn A. Bác muốn đi đến thị trấn B để thăm một
người bạn. Trong chuyến đi, bác sẽ đi qua N thị trấn 1, 2, 3, …, N. Các thị trấn này nằm
ở trên đường nối A đến B. Thị trấn j cách thị trấn A là Dj kilômét.
Bác quyết định sẽ mang theo N con lợn để bán tại mỗi thị trấn một con. Giá thịt
lợn tại N thị trấn này cũng khác nhau, tại thị trấn j là Pj đồng/kilogam.
N con lợn cũng có cân nặng khác nhau, con thứ j có cân nặng là Wj. Mang một
kilogam thịt lợn đi đoạn đường một kilomét sẽ làm tốn thêm t đồng để mua xăng.
Yêu cầu: Bạn hãy giúp bác John kiếm được nhiều tiền nhất bằng cách chỉ cho
bác nên bán con lợn nào tại thị trấn nào.
Dữ liệu vào: Đọc từ file văn bản PIGS.INP có cấu trúc như sau:
• Dòng thứ nhất ghi số N và t.
• Dòng thứ hai ghi N số Wj.
• Dòng thứ ba ghi N số Dj.
• Dòng thứ tư ghi N số Pj.
Các số cách nhau một dấu cách.
Dữ liệu ra: Đưa ra file văn bản PIGS.OUT có cấu trúc như sau:
• Chỉ có 1 dòng ghi ra N số, số thứ j là số hiệu của con lợn sẽ bán ở thị trấn thứ j.

đó là Mod 2004 .
SWE.INP SWE.OUT
2 1 3
3
5
9
Giới hạn:
 1 ≤ N ≤ 10
 0 ≤ a ≤ b ≤ 10 000 000 .
 0 ≤ A
i
≤ 1 000 000 .
------HẾT------
Chú ý: Cán bộ coi thi không giải thích gì thêm
Vòng 2 Trang 3