Đề thi học sinh giỏi môn Tin THPT năm 2012

Kì thi học sinh giỏi là kì thi quan trọng đối với mỗi học sinh. Dưới đây là đề thi học sinh giỏi môn Tin lớp 12 năm 2012 giúp các em kiểm tra lại đánh giá kiến thức của mình và có thêm thời gian chuẩn bị ôn tập cho kì thi sắp tới được tốt hơn.
Nội dung trích xuất từ tài liệu:
Đề thi học sinh giỏi môn Tin THPT năm 2012Họ tên TS : ......................................................... ... Số BD: ...................... Chữ ký GT 1 : .....................SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH NINH THUẬN NĂM HỌC 2011 – 2012 Khóa ngày: 17 / 11 / 2011 (Đề thi chính thức) Môn thi: TIN HỌC Lớp 12 THPT Thời gian làm bài: 180 phút (Không kể thời gian phát đề) ĐỀ: (Đề thi có 02 trang) TỔNG QUAN ĐỀ THI STT Tên bài File chương trình File dữ liệu vào File kết quả 1 RẮN HỔ MANG snail.* snail.inp snail.out 2 MA TRẬN VUÔNG ĐỐI XỨNG matrix.* matrix.inp matrix.out 3 ĐỔI TIỀN money.* money.inp money.out Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tươngứng là Pascal, Free Pascal ho ặc C++. Bài 1: (6 điểm) RẮN HỔ MANG Một con rắn hổ mang sống trên một lưới vuông 8 x 8 có chứa vài vật cản (là các ô màuđen trong hình vẽ dưới đây). Con rắn di chuyển theo đường thẳng (khi còn có thể di chuyểnđược). Khi nó gặp vật cản hay gặp biên của lưới vuông, nó sẽ quay sang ô bên trái nó. Nếu nóđối diện với ô đã đi qua, nó dừng hẳn. A B C D E F G H 1 r 2 3 4 5 6 7 8 Đường đi khi luôn quay qua trái (13 ô) Con rắn luôn bắt đầu tại ô A1, và luôn bắt đầu việc di chuyển bằng cách đi hướng xuốngdưới. Vị trí các vật cản (tức là các ô đen) được cho biết trước. Yêu cầu :Tìm số ô mà con rắn đi qua cho đến khi không đi được nữa và thỏa con rắnluôn đi về bên trái nó. Ví dụ: Hình vẽ trên cho hình ảnh một lưới vuông với ba ô đen (tại các vị trí A6, E2, F5).Đường đi con rắn luôn đi về bên trái nó là: đi từ A1 đến A5, quay sang trái đến E5. Từ E5quay sang trái đến E3, quay trái, đi thẳng và dừng ở B3. Con rắn đã đi qua 13 ô. Dữ liệu : Vào từ file văn bản snail.inp Dòng đầu tiên ghi số nguyên dương n là số các ô đen; Trên n dòng tiếp theo, mỗi dòng ghi tọa độ một ô đen dưới dạng Xm , trong đó X (là các chữ cái Latinh viết hoa từ A đến H) chỉ cột và m (1≤m≤ 8) chỉ dòng . Chú ý không có ô đen tại A1 và A2. Trang 1/2 Đề thi chính thức Kết quả: Ghi ra file văn bản snail.out số ô mà con rắn đi quaVí Dụ : snail.inp snail.out 3 13 A6 E2 F5Bài 2: (7 điểm) MA TRẬN VUÔNG ĐỐI XỨNG Cho ma tr ận vuông A kích thư ớc N x N ch ứa các s ố tự nhiên trong kho ảngtừ 0 đến 255; 4 ≤ N ≤ 50. Hãy tìm một ma trận vuông đối xứng có kích thước lớn nhất Btrong A theo nghĩa các phần tử đối xứng qua đường chéo chính của B thì bằng nhau. Dữ liệu : Vào từ file văn bản matrix.inp Dòng đầu ghi giá trị N. Tiếp đến là N dòng của ma trận A. Dữ liệu trên cùng một dòng cách nhau ít nhấtmột khoảng trắng. Kết quả : Ghi ra file văn bản matrix.out Gồm một dòng chứa ba giá trị i, j, d cách nhau ít nhất một khoảng trắng, trong đói, j cho biết vị trí (dòng i, cột j) đầu tiên của ma trận B cần tìm trong ma trận A, còn d cho biếtsố phần tử trên cùng một dòng của B. Chỉ số dòng và cột được tính từ 1 đến N. (nếu có nhiềuma trận vuông đối xứng cùng kích thước trong A thì chọn một trong số đó).Ví Dụ : matrix.inp matrix.out 4 2 1 3 7 6 8 9 1 2 3 0 2 4 5 7 3 5 6 9Bài 3: (7 điểm) ĐỔI TIỀN Có n loại tiền từ A1, A2,…..,A n. Hãy tìm cách dùng các loại tiền này để có số tiền L saocho tổng số tờ tiền là ít nhất. Dữ liệu : Vào từ ...