Đề thi HSG Quảng Ngãi NĂm 2005 (đề 1)

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN HSG TỈNH - THPT
QUẢNG NGÃI Năm học 2004-2005

Tên bài
Tên chương trình
Dữ liệu vào
Kết quả

BÀI 3
Phân tích
SUM.PAS
SUM.IN
SUM.OU

BÀI 4
Máy bay
AIRPLANE.PAS
AIRPLANE.IN
AIRPLANE.OU


Bài 3: Tính tổng Tên chương trình: SUM.PAS
Cho số nguyên dương S và tập A gồm N số nguyên dương a1, a2, ... aN, đôi một khác nhau và a1=1. Ta biết rằng S có thể viết thành tổng các phần tử trong tập A.
Hãy cho biết tổng này chứa ít nhất là bao nhiêu số hạng.
Ví dụ: Với S=14 và tập A gồm 6 phần tử là 1, 2, 3, 5, 7 , 10 thì có thể viết S theo nhiều phương án như sau:
S = 1 + 1 + 2 + 10 ( 4 số hạng )
S = 1 + 3 + 10 ( 3 số hạng )
S = 7 + 7 ( 2 số hạng )
.....
trong đó phương án thứ 3 là tối ưu vì chỉ dùng 2 số hạng.
Dữ liệu vào: tập tin văn bản SUM.IN, gồm:
Dòng đầu tiên là hai số nguyên dương S và n
Tiếp đến là giá trị a1, a2, ..., aN có thể viết trên nhiều dòng. Các số được viết cách nhau ít nhất một dấu cách. 1 ≤ S ≤ 10000, 1 ≤ N ≤ 100, a1=1 , dãy A được sắp tăng với các phần tử đôi một khác nhau.
Kết quả: Ghi vào tập tin văn bản SUM.OU một số nguyên dương k là số số hạng tối thiểu trong tổng biểu diễn của S.
sum.in
sum.ou

14 6
1 2 3
5 7 10
2


Bài 4: Máy bay Tên tập tin chương trình: AIRPLANE.PAS
Hình ảnh của máy bay với chỉ một lối vào bằng một hành lang xuyên qua tất cả các hàng của ghể và hành khách. Hành khách bước vào hành lang và tìm chỗ ngồi của họ.
Mỗi hành khách phải ngồi đúng ghế của mình và lối vào đến máy bay bắt đầu từ hàng ghế đầu tiên phía trước. Hành khách bước vào máy bay theo lần lượt từng người, không có sự dừng lại không cần thiết.
Hành khách đi bộ vào hành lang theo hướng ghế của mình và ở mỗi hàng ghế hành khách dừng lại đúng 1 giây (hoặc lâu hơn nếu phía trước họ là một hành khách khác) cho đến khi hành khách đến đúng hàng ghế của mình và hành khách dừng lại tại hàng ghế của mình được 5 giây (để cất, đặt hành lý). Trong mỗi giây trong hành lang, tại một hàng chỉ có thể có một hành khách.
Yêu cầu: Viết chương trình tính tất cả thời gian cần thiết để hành lang trong máy bay không còn hành khách, điều này có nghĩa là tất cả hành khách đã ngồi vào ghế của họ.
Dữ liệu vào: vào từ tập tin văn bản airplane.in:
Dòng đầu tiên ghi số nguyên N , là số hành khách, 1 ≤ N ≤ 1000
Dòng i+1 chứa số nguyên Ri là số hàng ghế mà ở đó hành khách thứ i phải ngồi, 1≤ Ri ≤ 1000.
Hành khách được đánh số từ 1 đến N và họ vào theo trật tự đó. Số lượng hành khách ngồi trên cùng một hàng là không có giới hạn.
Kết quả: ghi vào tập tin văn bản airplane.ou là một số nguyên T (tính bằng giây), là thời gian cần thiết để tất cả hành khách ngồi vào ghế của họ.
Ví dụ:
Airplane.in
Airplane.in

1
3
4
4
4
1
5

Airplane.ou
Airplane.ou

7
19

Bài 3
ses crt;
const
fn = `sum.in`; gn = `sum.ou`; hn = `sum.ts`;
mn = 10000; bl = #32; sotest = 5;
dapso : array[1..sotest] of integer = (4,9,2,11,69);
type ii = integer;
mw1 = array[0..mn+1] of ii;

var
f,g: text;
n,s:ii;
ch: char;
a,d: mw1;
soloi: ii;
diemtest: array[1..sotest] of ii;
tongdiem: ii;
bailam:ii;

procedure xem(var x: mw1);