---
THÀNH PHỐ HỒ CHÍ MINH
Đề thi chính thức
Đề thi có 02 trang
ĐỀ THI HỌC SINH GIỎI LỚP 12 THPT CẤP THÀNH PHỐ
KHOÁ THI NGÀY 09.03.2016
Trang 1
Môn thi: TIN HỌC
Thời gian: 150 phút
(Không kể thời gian phát đề)
TỔNG QUAN BÀI THI
Tên bài Tên chương trình Tập tin dữ liệu Tập tin kết quả
Bài 1 CỔ VẬT SAMPLE.* SAMPLE.INP SAMPLE.OUT
Bài 2 THU HOẠCH JACKFT.* JACKFT.INP JACKFT.OUT
Bài 3 PHÉP CỘNG ADD.* ADD.INP ADD.OUT
Dấu * được thay thế bởi PAS hay CPP của ngôn ngữ lập trình được sử dụng tương ứng là
Pascal hoặc C++.
Hãy lập trình giải 3 bài toán sau:
Bài 1: CỔ VẬT - SAMPLE (6 điểm)
Một nhà khảo cổ học đã vào trong một khu mộ cổ. Bằng kinh nghiệm của mình ông ta
nhìn ra ngay giá trị của các mẫu có trong khu mộ.Trong đó có N mẫu, mỗi mẫu có một khối
lượng Pi và một giá trị V
i
. Ông ta chỉ có M cái túi và mỗi túi chỉ chứa được 1 mẫu với khối
lượng tối đa C
i
Yêu cầu: Tính tổng giá trị tối đa của những mẫu mà nhà khảo cổ có thể mang về.
Dữ liệu vào: Cho trong tập tin văn bản SAMPLE.INP gồm:
- Dòng đầu 2 số nguyên N, M số mẫu và số túi của nhà khảo cổ.(1≤ N,M ≤ 300 000);
- N dòng sau, mỗi dòng gồm 2 số nguyên P
i
,V
i
lần lượt là khối lượng và giá trị của mỗi
mẫu. (1 ≤ Pi,Vi ≤ 1000000)
- M dòng kế tiếp, mỗi dòng gồm một số nguyên C
i
là khối lượng tối đa của túi tương
ứng có thể chứa. (1 ≤ Ci ≤ 100000000)
Kết quả: Ghi vào tập tin văn bản SAMPLE.OUT gồm một số duy nhất là tổng giá trị tối đa
mà nhà khảo cổ có thể mang về.
Ví dụ:
SAMPLE.INP SAMPLE.OUT
2 1
5 10
100 100
12
10
Giải thích: chỉ có thể lấy mẫu thứ nhất do túi của không chứa được mẫu thứ 2.
Bài 2: THU HOẠCH - JACKFT (7 điểm)
Đồng bằng sông Cửu Long là một vùng trù phú. Ngoài lúa còn có các loại cây ăn trái.
Nhà toán học Y có một trang trại tại vùng này và trang trại có nhiều cây mít. Nhưng cây mít
được trồng thẳng hàng và có tất cả N cây. Cây mít thứ i có vị trí là x
i
và có a
i
quả mít. Đến
mùa thu hoạch để tránh hái lầm, nhà toán học đưa người làm vườn Cuội đưa một sợi dây có
độ dài L và yêu cầu quấn quanh một số cây liên tiếp nhằm mục đích đánh dấu những cây sẽ
được thu hoạch. Biết rằng mỗi cây đều có bán kính thân là D.
Yêu cầu: Hãy viết chương trình giúp Cuội dùng sợi dây đánh dấu các cây mít sao cho tổng
số quả thu hoạch được là nhiều nhất và không được cắt sợi dây.
Dữ liệu: File vào JACKFT.INP gồm nhiều dòng:
- Dòng thứ nhất ghi 3 số nguyên dương N, L, D (N ≤ 10
Trang 2
5
, l ≤ 10
, k ≤ 100)
- Dòng thứ hai ghi N số nguyên x
i
là vị trí của cây mít thứ i (|x
i
)
- Dòng thứ ba ghi N số nguyên a
i
là số quả mít trên cây mít thứ i (a
i
6
| ≤ 10
9
<= 10
)
Kết quả: Ghi vào tập tin văn bản JACKFT.OUT một số nguyên duy nhất là số mít hái được.
Ví dụ:
JACKFT.INP JACKFT.OUT
5 10 1
1 7 3 4 6
5 1 3 5 6
14
Bài 3: PHÉP CỘNG – ADD (7 điểm)
Các nhà khảo cổ tìm được một số bản khắc các con số với môt số ký hiệu và khi ghép
lại họ thấy được một số biểu thức dạng A=S vô nghĩa. Nhưng trong lúc quan sát con của một
nhà khảo cổ thấy rằng đây là biểu thức đúng khi cho thêm một số dấu cộng giữa những chữ số
của A.
Bài toán: Cho biểu thức có dạng A = S. Hãy viết một chương trình thêm vào vế trái của biểu
thức trên một số lượng ít nhất các dấu cộng để có đuợc biểu thức đúng. (Chấp nhận có những
số có những số không phía trước trong biểu thức).
Dữ liệu vào: Từ tập tin văn bản ADD.INP gồm:
Một dòng duy nhất chứa biểu thức có dạng A=S. A và S đều là số nguyên dương không có số
không vô nghĩa ở đầu. A có tối đa 1000 chữ số và S ≤ 5000.
Kết quả: Ghi vào tập tin văn bản ADD.OUT cho biết biểu thức đúng.
Ví dụ:
ADD.INP ADD.OUT
2505=30 25+05=30
HẾT
GIÁM THỊ KHÔNG ĐƯỢC GIẢI THÍCH GÌ THÊM.
9
Không có nhận xét nào:
Đăng nhận xét
Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.