Luyện thi HSG Tin học THCS Đề số 3

Phòng giáo dục và Đào tạo
QUẬN hOÀN KIẾM
ĐÒ LUYỆN HỌC SINH GIỎI
Năm học: 2012 – 2013
Môn: Tin học THCS
Thời gian làm bài: 90 phút


Bài 1: (7 điểm) CHỌN PHẦN THƯỞNG
Trong kỳ thi học sinh giỏi môn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i có giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy. Em hãy lập chương trình chọn ra các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất.
Dữ liệu: cho file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N
- Dòng tiếp theo ghi N số ai (1 ≤ i ≤ N).
Kết quả: ghi ra file PTHUONG.OUT gồm hai dòng:
- Dòng đầu ghi tổng giá trị lớn nhất của các phần thưởng đã chọn và số lượng các phần tử được chọn đó.
- Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự trong dãy.
- Dòng cuối ghi giá trị của các phần thưởng đã chọn theo thứ tự trong dãy.
Ví dụ:
PTHUONG.INP
PTHUONG.OUT

7
6 9 1 3 5 10 4
32 5
1 2 4 6 7
6 9 3 10 4


Bài 2 (7 điểm): CÁC THANH GỖ
Trong một buổi cắm trại của lớp, bạn An mua N thanh gỗ hình chữ nhật, có độ dài bằng nhau. Khi cắm trại, các bạn của An đã cưa ngang các thanh gỗ đó ra thành các đoạn hình chữ nhật, có độ dài là số nguyên.
Về sau các bạn có ý định gắn các đoạn gỗ với nhau để khôi phục lại các thanh gỗ nhưng vì quên mất độ dài ban đầu nên họ quyết định nối lại các đoạn gỗ sao cho chúng có độ dài bằng nhau và càng ngắn càng tốt.
Gọi L là độ dài nhỏ nhất của các thanh gỗ và M là số thanh gỗ tạo thành.
Em hãy lập chương trình giúp họ chọn ra cách nối các đoạn gỗ với nhau theo yêu cầu trên.
Dữ liệu: cho trong file văn bản THANHGO.INP:
- Dòng đầu ghi số N (N(50) là số lượng các đoạn gỗ.
- Dòng tiếp theo ghi N số nguyên Li (1 ( Li ( 100, 1 ( i ( N) (Li là độ dài của đoạn gỗ thứ i).
Kết quả: Ghi ra màn hình và file văn bản THANHGO.OUT
- Dòng đầu ghi hai số L và M (ghi 0 nếu không tìm được cách nối phù hợp).
- Nếu M > 0, trên M dòng tiếp theo, dòng thứ i ghi độ dài các đoạn gỗ dùng để ghép thành thanh gỗ thứ i.
Ví dụ:
THANHGO.INP
THANHGO.OUT

10
2 3 5 2 7 4 6 1 3 3
9 4
3 6
7 2
5 4
3 3 2 1


Bài 3: (6 điểm) XẾP LỊCH LÀM BÀI
Một học sinh cần làm N bài tập được đánh số từ 1 đến N (1 ( N ( 100). Bài tập thứ i làm trong khoảng thời gian là Ai (1 ( i ( N, 1 ( Ai ( 100). Bài tập thứ i phải được làm trước bài tập thứ (i + 1). Trong một buổi có thể bố trí giải một hay nhiều bài tập. Thời gian tối đa của một buổi là L (1 ( L ( 150).
Hãy hãy lập chương trình xếp lịch giải hết các bài tập sao cho số buổi là ít nhất.
Dữ liệu: từ file LICH.INP gồm hai dòng:
- Dòng đầu ghi hai số N và L.
- Dòng cuối ghi N số A1. A2,..., An
Kết quả: ghi ra màn hình và file LICH.OUT theo quy cách sau:
- Dòng đầu ghi số buổi M (ghi 0 nếu không xếp lịch).
- Nếu M>0, trên M dòng tiếp theo, dòng thứ i ghi thời gian các bài trong buổi thứ i.
Ví dụ :
LICH.INP
LICH.OUT

10
120
60 60 5 30 10 10 20 30 80 60
4
60 60
5 30 10 10 20 30
80
60