DE THI OLYMPIC

SỞ GIÁO DỤC VÀ ĐÀO TẠO
VĨNH LONG
KỲ THI CHỌN HỌC SINH GIỎI VÒNG TỈNH THPT
NĂM HỌC 2014 – 2015




ĐỀ THI CHÍNH THỨC
Môn thi: TIN HỌC
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
Buổi thi thứ nhất: SÁNG 19/10/2014
(Đề thi có 03 trang, gồm 03 bài)


TỔNG QUAN BÀI THI BUỔI THỨ NHẤT


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

Bài 1
Chỉ thị
CHITHI.PAS
CHITHI.INP
CHITHI.OUT

Bài 2
Phân tích số
PHANTICH.PAS
PHANTICH.INP
PHANTICH.OUT

Bài 3
Cuộc đua
RACE.PAS
RACE.INP
RACE.OUT

Hãy lập trình giải các bài toán sau:
Bài 1. Chỉ thị (6 điểm)
Cho trước dãy số A gồm n số nguyên dương: A1, A2, …, An. Người ta yêu cầu thực hiện M thao tác trên dãy số đã cho. Mỗi thao tác là một chỉ thị thuộc một trong hai dạng:
Chỉ thị dạng 0 0 x mang ý nghĩa: Thêm vào cuối dãy A hiện tại một phần tử mới có giá trị là x.
Chỉ thị dạng 1 x y mang ý nghĩa: Tính tổng dãy con liên tiếp của dãy A hiện tại từ Ax đến Ay.
Ví dụ: Cho trước dãy A gồm 3 phần tử là 1, 2, 3. Xét 3 chỉ thị được yêu cầu thực hiện theo thứ tự từ trên xuống như sau:
0 0 4
0 0 5
1 2 5
Chỉ thị 0 0 4 yêu cầu thêm vào cuối dãy A hiện tại phần tử mới có giá trị là 4. Như vậy, sau khi thực hiện xong chỉ thị này thì dãy A gồm có 4 phần tử là 1, 2, 3, 4.
Chỉ thị 0 0 5 yêu cầu thêm vào cuối dãy A hiện tại phần tử mới có giá trị là 5. Như vậy, sau khi thực hiện xong chỉ thị này thì dãy A gồm có 5 phần tử là 1, 2, 3, 4, 5.
Chỉ thị 1 2 5 yêu cầu tính tổng dãy con liên tiếp của dãy A hiện tại từ A2 đến A5, nghĩa là tính tổng 2 + 3 + 4 + 5.
Hãy lập trình thực hiện M chỉ thị được yêu cầu. Khi gặp chỉ thị dạng 1 x y thì sau khi tính tổng, ghi ra tổng tính được.
Dữ liệu vào từ file văn bản CHITHI.INP gồm nhiều dòng:
Dòng đầu là hai số n, M (n, M ≤103);
Dòng thứ hai ghi dãy số A1, A2, …, An (|Ai|< 106)
M dòng tiếp theo ghi M chỉ thị cần thực hiện, mỗi chỉ thị ghi trên một dòng.
Các số trên cùng dòng viết cách nhau một dấu cách.
Kết quả ghi ra file văn bản CHITHI.OUT kết quả của các chỉ thị dạng 1 x y tương ứng trong file input, mỗi kết quả ghi trên một dòng.



Ví dụ:
CHITHI.INP
CHITHI.OUT

3 5
1 2 3
0 0 4
1 1 4
0 0 5
0 0 6
1 4 6
10
15


Bài 2. Phân tích số (7 điểm)
Cho dãy số A gồm n số nguyên: A1, A2, …, An và số nguyên M. Hãy cho biết có bao nhiêu cách phân tích số M thành tổng các số trong dãy, biết rằng trong một cách phân tích thì mỗi số Ai (1 ≤ i ≤ n) được sử dụng không quá một lần.
Ví dụ: Cho dãy số 1, -2, 3, 4, -3 và số nguyên M = 3; khi đó ta tìm được ba cách phân tích là:
(1) M = 1 - 2 + 4;
(2) M = 3;
(3) M = 1 – 2 + 3 + 4 - 3
Dữ liệu vào từ file văn bản PHANTICH.INP gồm hai dòng:
Dòng đầu ghi hai số nguyên n, M (1 ≤ n ≤ 17, |M| ≤ 106);
Dòng thứ hai ghi n số nguyên A1, A2, …, An (|Ai| ≤ 104);
Các số trên cùng dòng viết cách nhau một dấu cách.
Kết quả ghi ra file văn bản PHANTICH.OUT số lượng cách phân tích số M theo yêu cầu. Nếu không có cách phân tích nào thì ghi số 0.
Ví dụ:
PHANTICH.INP
PHANTICH.OUT

5 3
1 -2 3 4 -3
3

3 -5
-6 7 -8
0

Bài 3. Cuộc đua (7 điểm).
Một mạng giao thông có N thành phố đánh số từ 1 đến