Đề thi chọn học sinh giỏi Lớp 12 THPT môn Tin học - Năm học 2012-2013 - Sở GD&ĐT Ninh Bình (Đề 1) (Có đáp án)

ĐỀ THI CHÍNH THỨC
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
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/test
Ghi 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ập phâ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ố 5
Câ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 trong hộ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ất cả 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ất trong 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ện
Kế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 khi thự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.
7 4
1 3
2 6
1 6
1 2
4
Ban đầu: (1) (2) (3) (4) (5) (6) (7)
Chuyển 1 3: (2) (1 3) (4) (5) (6) (7)
Chuyển 2 6: (1 3) (4) (5) (2 6) (7)
Chuyển 1 6: (4) (5) (1 2 3 6) (7)
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á 109.
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 xi 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
0 0
1 1
1 0
0 1
4
Chú ý: 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 bao gồ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ới một số n trong file dữ liệu theo đúng thứ tự.
Ví dụ:
PASCAL.INP
PASCAL.OUT
3
3
8
11
4
2
8
Chú ý: 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:.......................................................................................................