De thi HSG Tin hoc tinh Nam Dinh 2011 2012

Sở giáo dục đào tạo Nam Định
Kỳ thi học sinh giỏi lớp 9
Năm học 2011 – 2012
Môn Tin học
Thời gian làm bài 150 phút

Bài 1. Giá trị biểu thức (6 điểm)
Cho một xâu chỉ chứa các kí tự: chữ số, dấu cộng, dấu trừ, thể hiện một biểu thức số học. Yêu cầu tính giá trị của biểu thức đã cho. Biết xâu biểu thức không quá 255 kí tự, các số hạng và giá trị của biểu thức có độ lớn không quá hai tỉ.
Dữ liệu vào từ tệp BT.inp chứa duy nhất một xâu kí tự thể hiện biểu thức cần tính.
Kết quả đưa ra tệp BT.out chứa một số nguyên là giá trị của biểu thức.
BT.inp
BT.out

12+3-7
8

Bài 2. Dãy biến động (7 điểm)
Dãy A được gọi là dãy biến động nếu phần tử thứ i thỏa mãn điều kiện:
A[i-1] < A[i] >A[i+1] hoặc A[i-1] > A[i] Với mọi i thuộc [2; k-1] trong đó k là số phần tử của A
Yêu cầu: Cho dãy X gồm n số nguyên (0Dữ liệu vào: từ tệp văn bản BD.out có cấu trúc
- Dòng 1 chứa số nguyên n là số phần tử của X
- Dòng 2 chứa n số nguyên của dãy X
Kết quả đưa ra tệp BD.out chứa số k là số phần tử của dãy Y thỏa mãn yêu cầu của bài, nếu không tồn tại thì đưa ra số 0.
BD.inp
BD.out

7
4 5 6 3 5 3 2
5

Bài 3. Buôn bán (7 điểm)
Công ty BB là công ty kinh doanh hàng tiêu dùng. Công ty BB mua hàng từ các đại lý ở thành phố HN vận chuyển bằng ô tô về phân phối cho các cửa hàng tại thành phố NĐ để bán phục vụ người tiêu dùng. Mỗi chuyến hàng chỉ chở được khối lượng m, với chi phí cho cả chuyến hàng là c. Có n mặt hàng, mặt hàng i có biết khối lượng pi, giá mua qi và giá bán ri. Số lượng các mặt hàng có đủ để cho công ty mua về nhưng tổng khối lượng của tất cả mặt hàng mua về không quá m. L là lợi nhuận thu được của một chuyến hàng được xác định: L = TB – TM – c
Trong đó TB là tổng số tiền bán của tất cả mặt hàng, TM là tổng số tiền mua của tất cả mặt hàng.
Yêu cầu: cho thông tin về các mặt hàng, hãy giúp công ty lập phương án mua các mặt hàng sao cho L lớn nhất.
Dữ liệu vào từ tệp BB.inp
- Dòng đầu ghi 3 số n, m và c (n, m, c nguyên dương nhở hơn 6001)
- n dòng tiếp theo, dòng thứ i ghi 3 số pi, qi, ri lần lượt là khối lượng, giá mua và giá bán của mặt hàng i (pi, qi, ri đều nguyên dương và nhỏ hơn 101).
Kết quả đưa ra tệp BB.out
- Dòng 1 ghi số L tìm được
- Nếu L > 0 thì đưa ra phương án mua hàng trong các dòng tiếp theo, mỗi dòng chứa hai số vi, si thể hiện mua hàng vi với số lượng si.
BB.inp
BB.out

3 10 5
3 1 8
5 5 16
1 1 3
18
1 3
3 1