Các đề luyện thi

HỘI THI TIN HỌC TRẺ ĐỀ THI BẢNG B – KHỐI THCS
TỈNH BÀ RỊA – VŨNG TÀU Thời gian làm bài 120 phút
Lần thứ XIX – 2015 Ngày thi: 28/06/2015
__oOo__ (Đề thi gồm 3 trang)
ĐỀ CHÍNH THỨC

TỔNG QUAN VỀ ĐỀ THI
Tên bài
Hệ trục tọa độ
Phát thưởng
Game

Tên file làm bài
COORDSYS.PAS
AWARDS.PAS
Game.PAS

Tên file dữ liệu
COORDSYS.INP
AWARDS.INP


Tên file kết quả
COORDSYS.OUT
AWARDS.OUT


Tổng điểm
20
40
40


Hướng dẫn làm bài:
Tên file làm bài, file dữ liệu và kết quả phải được đặt đúng theo yêu cầu của đề bài.
Thí sinh tạo thư mục trên đĩa cứng có tên “BSBD - Ho ten” (ví dụ: “B123 - Nguyen Van Anh”), tất cả các file làm bài đều lưu vào thư mục này.Trong đó, chữ B là tên bảng dự thi, 123 là số báo danh của bạn. Chú ý: họ tên đặt không dấu.
Không được ghi SBD, Họ tên hay các dấu hiệu đặc biệt gì khác vào file làm bài.

Bài 1. (20 điểm) Hệ trục tọa độ Tên file chương trình ‘COORDSYS.PAS’
Cho một dãy số nguyên có n phần tử a1, a2,… an. Người ta biểu diễn n số nguyên đó trên trục hoành (x’Ox)
Yêu cầu: Hãy cho biết phải cần dùng ít nhất bao nhiêu đơn vị độ dài trên trục x’Ox.
Ví dụ: dãy số có 5 phần tử là -2 5 9 4 7. Khi ta biểu diễn 5 số đó trên trục x’Ox thì ta phải dùng ít nhất là 11 đơn vị độ dài (xem hình).
/
Dữ liệu vào từ file COORDSYS.INP:
Dòng đầu là số nguyên dương n (n≤106).
Trong n dòng tiếp, dòng thứ i ghi số nguyên ai (|ai|≤109).
Kết quả ghi vào file COORDSYS.OUT một số nguyên duy nhất là đơn vị độ dài ít nhất trên trục x’Ox cần dùng.
Ví dụ:
COORDSYS.INP

COORDSYS.OUT

5
-2
5
9
4
7

11





Bài 2. (40 điểm) Phát thưởng Tên file chương trình ‘AWARDS.PAS’
Trường THCS XYZ có tổ chức một cuộc thi lập trình giao lưu với hình thức rất mới lạ. Một trong các phần mới lạ phải kể đến là ban tổ chức đang xem xét một phương án phát thưởng mới, theo đó phần thưởng chưa chắc được trao cho những thí sinh có điểm cao nhất. Thay vào đó, một thí sinh nếu nhận được phần thưởng thì phần thưởng đó phải có giá trị bằng điểm số của thí sinh này bất kể số điểm là thấp hay cao (dĩ nhiên phải lớn hơn 0).
Trong cuộc thi có n thí sinh, sau khi cuộc thi kết thúc thì n thí sinh có các điểm số lần lượt là các số nguyên dương a1, a2,… an. Ban tổ chức cũng đã dự trù tổng giá trị tiền thưởng là k đồng (k cũng là số nguyên dương). Ban tổ chức muốn dùng số tiền đó cho việc phát thưởng sao cho được nhiều thí sinh nhận thưởng nhất.
Ví dụ: với số tiền dự trù là 12 đồng và có 4 thí sinh dự thi với điểm số lần lượt là 8, 10, 1, 2.
Dễ thấy chọn 3 thí sinh có số điểm là 8, 1, 2 sẽ được nhiều thí sinh nhất.
Yêu cầu: Bạn hãy giúp ban tổ chức xác định số lượng nhiều nhất các thí sinh được nhận thưởng.
Dữ liệu vào từ file ‘AWARDS.INP’ gồm:
Dòng thứ nhất là số nguyên dương n là số thí sinh và k là số tiền dự trù của Ban tổ chức dùng cho việc phát thưởng (n≤105; k≤1018)
Dòng thứ hai chứa các số nguyên dương n dòng tiếp theo, dòng thứ i chứa số nguyên dương a1, a2,… an (ai≤109; i=1, 2,… n)
Kết quả ghi vào file ‘AWARDS.OUT’ một số nguyên duy nhất là số thí sinh nhiều nhất có thể được nhận thưởng.
Ví dụ:
AWARDS.INP

AWARDS.OUT

4 12
8 10 1 2

3


Bài 3. (40 điểm) Game Tên file chương trình ‘GAME.PAS’
Một trò chơi giữa người và máy gồm có N ô ( N chẵn và N
1000), đánh số thứ tự từ 1 tới N. Mỗi ô chứa một số nguyên dương ai (0 < ai≤ 100000). Bạn là người đi trước, tại mỗi lượt chơi người chơi sẽ lựa chọn ô ngoài cùng bên phải hoặc bên trái của dãy ô số