Đề tin HSG trường 11

ĐỀ THI CHÍNH THỨC HỌC SINH GIỎI CẤP QUỐC GIA NĂM 2007
MÔN TIN HỌC
Thời gian:180’ (không kể thời gian giao đề)
Ngày thi: 08/02/2007
Bài 1 (6 điểm). Dãy con không giảm dài nhất
Cho dãy số nguyên dương a1, a2, …, an.
Dãy số
ai, ai+1, …, aj thỏa mãn ai
ai+1
...
aj,
với 1
i
j
n được gọi là dãy con không giảm của dãy số đã cho và khi đó số j-i+1 được gọi là độ dài của dãy con này.

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số{uk} xác định bởi u1 = 1, uk = uk-1 + k (k
2), hãy tìm dãy con có độ dài lớn nhất.

Dữ liệu: Vào từ file văn bản MAXISEQ.INP
Dòng dầu tiên chứa một số nguyên duqoqng n (n
104);
Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ai (ai
108 là số hạng thứ i của dãy số đã cho, i = 1, 2, …, n.

Kết quả: Ghi ra file văn bản MAXISEQ.OUT số nguyên d là độ dài của dãy con thong giảm tìm được (quy ước rằng không có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0).

Ví dụ: Cho dãy số có 8 phần tử: 2, 2007, 6, 6, 15, 16, 3, 21. Các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy{uk} là: 6, 6, 15 và 3, 21 (vì u2 = 3, u3 = 6, u5 = 15, u6 = 21). Dãy số cần tìm là 6, 6,15 có độ dài là 3.

MAXISEQ.INP
MAXISEQ.OUT

8
2
2007
6
6
15
16
3
21
3


Bài 2 (7 điểm). Siêu thị may mắn
An được mời tham gia trò chơi “Siêu thị máy tính” do đài truyền hình ZTV tổ chức. Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là ci đồng, i = 1, 2, …, n. Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có gí trị là s đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là mi, i = 1, 2, …, n. An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n, s, ci va mi (1
n
500; 1
s
105; 1
ci
104; 1
mi
100) với i = 1, 2, …, n.

Dữ liệu: Vào từ file văn bản SMARKET.INP
Dòng đầu tiên chứa hai số nguyên dương s và n;
Dòng thứ i trong n dòng tiếp theo chứa 2 số nguyên dương ci và mi với i = 1, 2, …, n.

Kết quả: Ghi ra file văn bản SMARKET.OUT
Dòng đầu tiên ghi số nguyên d là tổng số cách mua hàng tìm được;
Nếu d
1 thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy n số nguyên, trong dó số hạng thứ i là số lượng mặt hàng thứ i mua được trong cách mua hàng này, i = 1, 2, …, n.

Hai số liên tiếp trên một dòng trong file dữ liệu và file kết quả cách nhau ít nhất một dấu cách.

Ví dụ:
SMARKET.INP
SMARKET.OUT

12 3
4 1
6 2
2 1
2
0 2 0


Bài 3 (7 điểm). Robot cứu hỏa
Trên một mạng lưới giao thông có n nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai chiều). Ta gọi đường di từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng:
S = u1, e1, u2, …, ui, ei, ui+1, …, ek-1, uk = t,
Trong đó u1, u2, ..., uk là các nút trong mạng lưới giao thông, ei là đường nối trực tiếp giữa nút ui và ui+1 (không có nút ui nào xuất hiện nhiều hơn một lần trong