Đề thi HSG Tin học 9 huyện Lập Thạch năm 2015-2016

PHÒNG GD&ĐT LẬP THẠCH ĐỀ THI KHẢO SÁT ĐỘI TUYỂN HSG LỚP 9 NĂM HỌC 2015-2016 MÔN: TIN HỌC Thời gian: 150 phút (Không kể thời gian phát đề ) (Lưu ý: Đề thi gồm 2 trang, học sinh đặt đúng tên file theo yêu cầu) Tên bài Dữ liệu TỔNG QUAN: Kết quả Giới hạn Dồn bi DonBi.Inp DonBi.Out s/test Đoán số DoanSo.Inp DoanSo.Out s/test Nuôi thỏ NuoiTho.Inp NuoiTho.Out s/test Điểm Lập chương trình giải các bài toán sau: Bài 1. Dồn bi (DonBi.Pas) Những lúc rảnh rỗi, Tùng thường ngồi chơi một mình trò chơi dồn bi như sau:  Tùng xếp hộp bi thành một hàng dài, đánh số theo chiều từ trái sang phải. Số bi ban đầu ở hộp thứ i là , có thể có hộp bi không có bi.  Ở mỗi lượt chơi, Tùng chọn hộp bi nào đó còn ít nhất hai viên bi, nhặt hai viên bi ra khỏi hộp , bỏ đi một viên, đặt một viên vào hộp  . Tùng sẽ thực hiện lượt chơi liên tục cho đến khi không thể chơi tiếp được nữa. Sau một thời gian, Tùng nảy ra ý định sẽ chơi sao cho dồn được nhiều bi nhất về hộp bi . Để kiểm tra xem mình có chơi tối ưu hay không, Tùng nhờ bạn lập chương trình xác định số lượng bi lớn nhất có thể có ở hộp 1 khi kết thúc trò chơi. Dữ liệu: (DonBi.Inp)  Dòng 1: Số nguyên  Dòng 2: số nguyên Kết quả: (DonBi.Out)  Dòng : Số nguyên là số bi nhiều nhất có thể có ở hộp khi kết thúc trò chơi. Ví dụ: DonBi.Inp DonBi.Out 4 0 2 4 8 3 Bài 2. Đoán số (DoanSo.Pas) Tùng và Sơn chơi trò chơi đoán số như sau:  Tùng chọn lấy hai số nguyên dương M, N (M>N) rồi thông báo cho Sơn biết một dãy số thỏa mãn: Trong dãy có một phần tử bằng tổng M+N, một phần tử khác bằng hiệu M-N 1 Nhiệm vụ của Sơn là đoán hai số M, N. Trò chơi khá khó nhưng sau nhiều lần chơi, Sơn biết được Tùng rất thích chọn cặp số giá trị lớn. Vì vậy, để tính toán dễ hơn, trong mỗi ván chơi Sơn sẽ cho bạn biết dãy số Tùng đưa ra và nhờ bạn xác định tích P = M x N lớn nhất có thể phù hợp với dãy đó (nghĩa là tồn tại cặp số (M, N) sao cho tích của chúng bằng P mà tổng và hiệu của chúng đều xuất hiện trong dãy Tùng đưa ra). Dữ liệu: (DoanSo.Inp)  Dòng 1: Số nguyên là số phần tử của dãy Tùng đưa ra;  Dòng 2: N số nguyên dương đôi một phân biệt là các phần tử dãy Tùng đưa ra, các số đều trong phạm vi 1..100. Kết quả: (DoanSo.Out)  Dòng 1: số nguyên là tích lớn nhất tính được. Số này chắc chắn tồn tại vì Tùng không bao giờ chơi gian dối. Ví dụ: DoanSo.Inp DoanSo.Out 3 6 1 4 5 Bài 3. Nuôi thỏ (NuoiTho.PAS) Sơn đến thăm chị Hằng và rất thích đàn thỏ chị nuôi. Sơn ngỏ ý xin chị Hằng một số con về chăm sóc. Hằng Nga đồng ý và cho phép Sơn chọn số lượng thỏ tùy ý trong số N thỏ (đánh số 1, 2, 3, …, N có trong chuồng. Ngoài ra, Hằng Nga cũng cho Sơn biết một số thông tin về cách nuôi thỏ như sau:  Nếu sống một mình trong chuồng, thỏ i ăn ai củ cà rốt mỗi ngày;  Nếu sống cùng thỏ khác nữa, thỏ i đòi ăn thêm bi củ cà rốt mỗi ngày ứng với mỗi thỏ cùng chuồng. Chẳng hạn, nếu nuôi ba thỏ cùng chuồng mà các cặp (ai,bi) tương ứng là (5;0), (2;2), (5; 1), số cà rốt lũ thỏ ăn mỗi ngày sẽ là: (5 + 0 x 2) + (2 + 2 x 2) + (5 + 1 x 2) = 18. Sơn muốn nuôi càng nhiều thỏ càng tốt, nhưng cậu chỉ có một cái chuồng nhốt thỏ và mỗi ngày cậu chỉ chuẩn bị được không quá M củ cà rốt. Sơn muốn nhờ bạn xác định giúp: Cậu nên xin Hằng Nga nhiều nhất là bao nhiêu thỏ mà vẫn đủ khả năng chăm sóc chúng. Dữ liệu: (NuoiTho.Inp)  Dòng 1: Hai số nguyên  Dòng 2 ... N+1: Dòng i+1 ghi hai số nguyên . Kết quả: (NuoiTho.Out)  Dòng 1: Số nguyên là số thỏ nhiều nhất Sơn nên xin. Ví dụ: NuoiTho.Inp NuoiTho.Out 4 19 3 5 0 2 2 5 1 1 4  2 =Hết= (Cán bộ coi thi không giải thích gì thêm) Họ và tên học sinh:……………………………………. SBD:…………………… 3