Tài liệu đề thi thực hành chọn học sinh giỏi tin lớp 12 v3

SỞ GIÁO DỤC – ĐÀO TẠO AN GIANG  ĐỀ THI CHỌN ĐỘI TUYỂN THI HSG CẤP QUỐC GIA Khoá ngày 25/10/2013 ĐỀ CHÍNH THỨC Môn thi : TIN HỌC Thời gian : 180 phút (không kể thời gian phát đề) Ngày thi thứ nhất: 25/10/2013 SBD:...............PHÒNG:....... ..... TỔNG QUAN NGÀY THI 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 Bài 2 Số cấp cộng Tạo số nguyên BAI1.PAS BAI2.PAS SHORTEN.INP SHORTEN.OUT Bài 3 Xếp ba lô BAI3.PAS BALO.INP BALO.OUT Bài 1 : (6 điểm) Số cấp cộng Viết chương trình nhập vào 2 số nguyên m, n, 100 ≤ m ≤ n ≤ 1000. Hãy đếm và in ra màn hình các số tự nhiên lẻ có 3 chữ số trong khoảng từ m đến n. Ba chữ số này, theo thứ tự từ trái qua phải tạo thành một cấp số cộng. Ví dụ : m = 100 ; n = 250  Co m Co m Co 5 = 0 = 1 so tu 100 den 250 thoa yeu cau: 111, 123, 135, 147, 159, 200 ; n = 300  so tu 200 den 300 thoa yeu cau: 800 ; n = 960  so tu 800 den 960 thoa yeu cau: 951, Bài 2 : (7 điểm) Tạo số nguyên Cho số nguyên N, 1 ≤ N ≤ 1000. Hãy xác định chữ số nhận được sau quá trình thu gọn số N1 theo yêu cầu sau: số nguyên N1 được tạo bằng cách viết liên tiếp nhau các số nguyên từ 1 đến N. Ví dụ: với N = 10, ta có N1 = 12345678910. Người ta thu gọn N1 bằng cách lần lượt xóa tất cả các chữ số ở vị trí chẳn, sau đó xóa tất cả các chữ số ở vị trí lẻ, rồi lại xóa các chữ số ở vị trí chẳn,… cho đến khi chỉ còn lại một chữ số: 12345678910  135790  370  30  0 Dữ liệu: vào từ tệp văn bản SHORTEN.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên N. Kết quả: Ghi ra tệp văn bản SHORTEN.OUT các chữ số còn lại ứng với các dữ liệu vào, mỗi chữ số đưa ra trên một dòng. Ví dụ: SHORTEN.INP 20 19 4 11 1 14 SHORTEN.OUT 0 0 3 0 1 0 Đề thi chọn đội tuyển thi HSG quốc gia – Môn Tin học Trang 1/2 Bài 3 : (7 điểm) Xếp ba lô Một nhà buôn cần sắp xếp N mặt hàng vào túi để mang về (N ≤ 100), với mỗi mặt hàng đều biết trọng lượng và giá trị của nó. Bạn hãy giúp nhà buôn lấy các mặt hàng để xếp vào một ba lô có sức chứa tối đa là M sao cho giá trị chứa trong ba lô là lớn nhất. Giả thiết là có thể lấy một tỉ lệ tuỳ ý ở mỗi mặt hàng. Dữ liệu vào (Input) từ tệp văn bản tên BALO.INP: Dòng 1: hai giá trị nguyên dương N và M.  N dòng tiếp theo, mỗi dòng chứa hai giá trị nguyên dương d, v cho mỗi vật dụng, trong đó d là trọng lượng, v là giá trị tính theo một đơn vị trọng lượng của vật đó (đơn giá). Các số cách nhau qua dấu cách.  Kết quả (Output) ghi ra tệp văn bản BALO.OUT:  N dòng, dòng thứ i cho biết trọng lượng cần lấy ở vật thứ i.  Dòng cuối cùng ghi tổng giá trị thu được. Ví dụ: BALO.INP 6 40 8 5 15 12 7 4 6 7 5 20 10 4 BALO.OUT 8 15 0 6 5 6 386 BALO.INP 5 25 4 3 7 10 8 6 9 9 7 1 BALO.OUT 1 7 8 9 0 202 * Ghi chú: - Thí sinh không được sử dụng tài liệu. - Cán bộ coi thi không giải thích gì thêm. -------Hết------- Đề thi chọn đội tuyển thi HSG quốc gia – Môn Tin học Trang 2/2 SỞ GIÁO DỤC – ĐÀO TẠO AN GIANG  ĐỀ THI CHỌN ĐỘI TUYỂN THI HSG CẤP QUỐC GIA Khoá ngày 25/10/2013 ĐỀ CHÍNH THỨC Môn thi : TIN HỌC Thời gian : 180 phút (không kể thời gian phát đề) Ngày thi thứ hai: 26/10/2013 SBD:...............PHÒNG :....... ..... TỔNG QUAN NGÀY THI THỨ HAI Tên bài File chương trình Bài 4 Chia đoạn BAI4.PAS File dữ liệu vào DOAN.INP File kết quả DOAN.OUT Bài 5 Số nguyên tố cùng độ cao BAI5.PAS PRIMES.INP PRIMES.OUT Bài 6 Chuyển bóng BAI6.PAS BALLS.INP BALLS.OUT Bài 4: (6 điểm) Chia đoạn Cho N số tự nhiên a1, a2, ..., a n (N  200). Bạn hãy tìm cách chia dãy N thành nhiều đoạn nhất sao cho mỗi đoạn có tổng các số bằng nhau. Dữ liệu: nhận vào từ tệp văn bản DOAN.INP  Dòng đầu tiên ghi số N.  Dòng còn lại ghi các số a1, a2, ..., an. Các số trên cùng một dòng cách nhau 1 khoảng cách. Kết quả: Ghi ra file DOAN.OUT  Dòng đầu tiên hai số h và s (trong đó h là số đoạn chia được; s là tổng giá trị các số của mỗi đoạn).  h dòng còn lại, mỗi dòng ghi theo thứ tự các số của mỗi đoạn chia được. Các số trên cùng một dòng cách nhau một khoảng cách. Ví dụ: DOAN.INP 6 3 0 2 1 4 2 Bài 5: (7 điểm) Số DOAN.OUT 2 6 3 0 2 1 4 2 DOAN.INP 6 2 3 1 0 2 DOAN.OUT 1 8 2 3 1 0 2 nguyên tố cùng độ cao Viết chương trình tìm và liệt kê các số nguyên tố có cùng độ cao không vượt quá n và có độ cao h, với n và h là hai số tự nhiên cho trước và 10  n  1000000; 1  h  54. Dữ liệu: nhận vào từ tệp văn bản PRIMES.INP, chứa hai số n và h. Kết quả: liệt kê các số nguyên tố cùng độ cao h, mỗi số nằm trên một dòng và ghi ra tệp văn bản PRIMES.OUT. Ví dụ: PRIMES.INP 200 14 PRIMES.OUT 59 149 167 Đề thi chọn đội tuyển thi HSG quốc gia – Môn Tin học PRIMES.INP 500 16 PRIMES.OUT 79 97 277 349 367 439 457 Trang 1/2 Bài 6: (7 điểm) Chuyển bóng Trên một bảng chia 2n+1 ô người ta đặt n quả bóng xám liền nhau, mỗi ô 1 quả, sau đó bỏ một ô trống và đặt tiếp n quả bóng trắng như Hình a. Hãy tìm cách chuyển với số lần ít nhất để thu được Hình b. Mỗi lần được phép chuyển một quả bóng vào ô trống kề quả bóng đó hoặc cách quả bóng đó 1 ô. Hình a Hình b Dữ liệu: vào từ tệp văn bản BALLS.INP, chứa số n. Kết quả: Ghi ra tệp văn bản BALLS.OUT • Dòng đầu tiên: cấu hình xuất phát là một xâu gồm N kí tự 'G' biểu thị bóng xám (Grey), tiếp đến là 1 kí tự 'B' biểu thị ô trống (Blank), tiếp đến là N kí tự 'W' biểu thị bóng trắng (White). • M dòng tiếp theo mỗi dòng là một cấu hình sau mỗi lần chuyển. • Dòng cuối cùng: số M – tổng số lần chuyển. Ví dụ: BALLS.INP BALLS.OUT 3 GGGBWWW GGBGWWW GGWGBWW GGWGWBW GGWBWGW GBWGWGW BGWGWGW WGBGWGW WGWGBGW WGWGWGB WGWGWBG WGWBWGG WBWGWGG WWBGWGG WWWGBGG WWWBGGG 15 BALLS.INP 2 BALLS.OUT GGBWW GBGWW GWGBW GWGWB GWBWG BWGWG WBGWG WWGBG WWBGG 8 -------Hết------- * Ghi chú: - Thí sinh không được sử dụng tài liệu. - Cán bộ coi thi không giải thích gì thêm. Đề thi chọn đội tuyển thi HSG quốc gia – Môn Tin học Trang 2/2