Đề thi chọn HSG Tin học 12 năm 2012-2013

Đề thi chọn học sinh giỏi Tin học 12 năm 2012-2013 dành cho học sinh và giáo viên tham khảo, giúp các em phát triển và tư duy năng khiếu của mình, nhằm giúp bạn củng cố kiến thức luyện thi học sinh giỏi đạt kết quả cao.
Nội dung trích xuất từ tài liệu:
Đề thi chọn HSG Tin học 12 năm 2012-2013 SỞ GD&ĐT NINH BÌNH ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 ĐỀ THI CHÍNH THỨC MÔN: TIN HỌC Ngày thi: 09/10/2012 (Thời gian làm bài:180 phút ) Đề thi gồm 04 câu, trong 02 trang Tổng quan đề thi: Câu Tên file bài làm Tên file Input Tên file Otput Thời gian chạy 1 NUMBER.PAS NUMBER.INP NUMBER.OUT 1 giây/test 2 GOMBI.PAS GOMBI.INP GOMBI.OUT 1 giây/test 3 TRIANGLE.PAS TRIANGLE.INP TRIANGLE.OUT 2 giây/test 4 PASCAL.PAS PASCAL.INP PASCAL.OUT 1 giây/testGhi chú: Thí sinh phải đặt tên file bài làm, file Input, file Output theo quy định như trên.Câu 1: Chữ số thứ N. Khi viết các số tự nhiên tăng dần từ 1, 2, 3,… liên tiếp nhau, ta nhận được một dãy các chữ số thậpphân vô hạn, đoạn đầu tiên của dãy sẽ là: 1234567891011121314151617181920...Yêu cầu: Hãy tìm chữ số thứ N của dãy số vô hạn trên.Dữ liệu: Cho trong file NUMBER.INP gồm một nguyên dương N (N < 106).Kết quả: Ghi kết quả ra file NUMBER.OUT.Ví dụ: NUMBER.OUT NUMBER.OUT Giải thích kết quả 21 5 Chữ số thứ 21 trong dãy là chữ số 5Câu 2: Gom bi. Có N cái hộp đánh số từ 1 tới N và N viên bi cũng đánh số từ 1 tới N. Ban đầu bi số i đặt tronghộp đánh số i (i = 1..N). Với một cặp số nguyên (u, v) cho trước, bạn phải thực hiện thao tác chuyển tấtcả các bi cùng hộp với bi có số u vào hộp chứa bi số v.Yêu cầu: Cho số N và danh sách M thao tác cần phải thực hiện. Hãy xác định số lượng bi lớn nhấttrong một hộp sau khi đã thực hiện đủ M thao tác chuyển bi.Dữ liệu: Cho trong file GOMBI.INP  Dòng 1 là hai số N, M (2 ≤ N ≤ 500; 1 ≤ M ≤ 1000).  M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v thể hiện một thao tác cần thực hiệnKết quả: Ghi ra file GOMBI.OUT một số nguyên là số lượng bi trong hộp có nhiều bi nhất sau khithực hiện các thao tác.Ví dụ: GOMBI.INP GOMBI.OUT Giải thích: Các hộp có bi sau mỗi lần chuyển. 74 4 Ban đầu: (1) (2) (3) (4) (5) (6) (7) 13 Chuyển 1 3: (2) (1 3) (4) (5) (6) (7) 26 Chuyển 2 6: (1 3) (4) (5) (2 6) (7) 16 Chuyển 1 6: (4) (5) (1 2 3 6) (7) 12 Chuyển 1 2: (4) (5) (1 2 3 6) (7)Câu 3: Tam giác cân. Cho hệ trục tọa độ Oxy, trên đó có đánh dấu n điểm (3 ≤ n ≤ 1500). Điểm thứ i có tọa độ (xi, yi)(i = 1 ÷ n), các tọa độ là số nguyên có giá trị tuyệt đối không vượt quá 10 9.Yêu cầu: Xác định số tam giác cân có ba đỉnh là ba điểm trong số n điểm đã cho.Dữ liệu: Cho trong file TRIANGLE.INP:  Dòng đầu tiên chứa số nguyên n.  Dòng thứ i trong n dòng sau chứa 2 số nguyên x i và yi.Kết quả: Ghi ra file TRIANGLE.OUT số tam giác cân tìm được.Ví dụ: TRIANGLE.INP TRIANGLE.OUT 4 4 00 11 10 01Chú ý: Trong 60% số test có n < 200.Câu 3(6 điểm): Tam giác PASCAL. Tam giác Pascal là một cách sắp xếp các hệ số khi khai triển nhị thức Newton vào một hình códạng tam giác theo từng hàng, các hàng được đánh số bắt đầu từ 0, hàng thứ n (n ≥ 0) của tam giác baogồm các hệ số trong khai triển của (x + y)n viết lần lượt từ trái sang phải. Dòng 0: (x + y)0 = 1 Dòng 1: (x + y)1 = 1.x + 1.y Dòng 2: (x + y)2 = 1.x2 + 2.xy + 1.y2 Dòng 3: (x + y)3 = 1.x3 + 3.x2y + 3.xy2 + 1.y3 … Dưới đây các hàng từ 0 đến 16 của Tam giác Pascal:Yêu cầu: Cho số tự nhiên n. Hãy tính số lượng số hạng là số lẻ trên dòng thứ n của tam giác Pascal.Dữ liệu: Cho trong file PASCAL.INP cấu trúc như sau: dòng đầu là số nguyên k < 10 là số lượng số n,k dòng tiếp theo mỗi dòng ghi một số n (1< n < 2.109)Kết quả: Ghi ra file PASCAL.OUT k dòng, mỗi dòng một số nguyên là kết quả bài toán tương ứng vớimột số n trong file dữ liệu theo đúng thứ tự.Ví dụ: PASCAL.INP PASCAL.OUT 3 4 3 2 8 8 11Chú ý: Trong 40 % số test có n < 30; trong 70% số test có n < 5000. -----------------------------Hết--------------------------Họ và tên thí sinh :....................................................... ……………..Số báo danh .............................Họ và tên, chữ ký: Giám thị 1:...................................................................................................... Giám thị 2:....................................................................................................... HƯỚNG DẪN CHẤM THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 MÔN: TIN HỌCChấm bằng chương trình tự động AMM2: Câu 1: 10 test, mỗi test đúng cho 0,5 điểm. Câu2: 10 test, mỗi test đúng cho 0,5 điểm. Câu3: 10 test đầu, mỗi test đúng cho 0,3 điểm. 10 test s ...