Đề thi HSG Tin 9 huyện Bình Xuyên năm 2016-2017

PHÒNG GD VÀ ĐT BÌNH XUYÊN ——————— (Đề thi gồm 02 trang) KỲ THI KHẢO SÁT HSG LỚP 9 NĂM HỌC 2016-2017 ĐỀ THI MÔN: TIN HỌC Thời gian làm bài: 150 phút, không kể thời gian giao đề. Lập chương trình giải các bài toán sau: Bài 1. (COUNT.PAS) Cho một chuỗi S chỉ gồm các kí tự trong bảng chữ cái thường và khoảng trắng. Nhiệm vụ của bạn là xác định độ dài lớn nhất của từ nằm trong chuỗi S đó, biết các từ được ngăn cách với nhau bởi một hay nhiều khoảng trắng. Dữ liệu từ file COUNT.inp: Chuỗi S có độ dài không quá 105 Dữ liệu ghi ra file COUNT.out: Số nguyên duy nhất là kết quả bài toán. COUNT.inp COUNT.out ahihihi do ngoc abc xyz 7 3 Bài 2. (CAL.PAS) Cho một ma trận vuông kích thước NxN, người ta điền các số từ 1 tới N 2 vào ma trận theo hình zigzag bắt đầu từ phía trên bên trái cho đến phía dưới bên phải. Ví dụ cho n = 4 thì ma trận zigzag như sau: Ví dụ. Cho n = 4 thì ma trận zigzag như sau: 1 2 6 7 3 5 8 4 9 1 0 1 1 1 2 1 5 1 3 1 4 1 6 Hướng đi của hình zigzag với N = 4 : Một ví dụ khác với N = 6: 1 2 6 7 15 16 3 5 8 14 17 26 4 9 13 18 25 27 10 12 19 24 28 33 11 20 23 29 32 34 21 22 30 31 35 36 Cho hai loại yêu cầu:  Với yêu cầu đầu tiên, cho một số nguyên k, xác định tọa độ vị trí của k trong bảng trên.  Với yêu cầu thứ hai, cho hai số nguyên (x,y), xác định giá trị của ô (x, y) trong bảng NxN. Dữ liệu từ file CAL.inp: Dòng 1: Số nguyên Q, là loại yêu cầu (1<=Q<=2). Với Q = 1: o Dòng 2: Số nguyên N (1<=N<=106). 1 o Dòng 3: Số nguyên K (1<=K<=N*N) Với Q = 2 o Dòng 2: Một số nguyên N (1<=N<=106). o Dòng 3 : Gồm hai số nguyên x và y (1<=x, y <= N). Dữ liệu ghi ra file CAL.out:  Với yêu cầu 1, in ra hai số nguyên (x,y) là tọa độ cần tìm  Với yêu cầu 2, in ra số nguyên duy nhất là giá trị tại ô đã cho CAL.inp CAL.out 1 4 3 21 2 5 43 19 Bài 3. (DETERMINE.PAS) Cho dãy A gồm N phần tử A1 … AN và M câu truy vấn, mỗi câu truy vấn gồm hai số nguyên l và r. Nhiệm vụ của bạn là phải xác định xem đoạn con A l, Al+1, …, Ar có phải là dãy thang hay không. Dãy B1… Bk gọi là dãy thang nếu tồn tại ít nhất một vị trí x thỏa mãn: B1<= B2<=…<=Bx>=Bx+1 >=Bx+2…>=Bk. Lưu ý là dãy tăng dần (ví dụ 1,3,6) hay dãy giảm dần (ví dụ 6,2,1) cũng là dãy thang. Dữ liệu từ file DETERMINE.inp: Dòng 1: Gồm hai số nguyên N và M (1<=N, M <= 10 5). Dòng 2: Gồm N số nguyên A1 … AN (1<=Ai<= 109) M dòng tiếp theo, mỗi dòng gồm hai số nguyên l và r (1<=l, r <= N). Dữ liệu ghi ra file DETERMINE.out: Gồm M dòng, nếu đáp án của truy vấn thứ i là dãy thang thì in ra “Yes”, ngược lại in ra “No”. DETERMINE.inp 10 10 4726481219 6 10 19 99 28 99 11 88 48 88 77 DETERMINE.out No No Yes No Yes Yes Yes No Yes ------------- HẾT ------------- 2