Đề thi chọn học sinh giỏi lớp 12 năm 2010-2011 môn Tin học - vòng 2

Chia sẻ: Nguyễn Như Phượng | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

113
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn trau dồi kiến thức cho các kỳ thi học sinh giỏi môn Tin học lớp 12, Đề thi chính thức chọn học sinh giỏi lớp 12 THPT năm 2010 - 2011. Môn Tin học của sở GD&DT tỉnh Ninh Bình. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi chọn học sinh giỏi lớp 12 năm 2010-2011 môn Tin học - vòng 2

SỞ GIÁO DỤC VÀ ĐÀO ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT TẠO NĂM HỌC 2010 - 2011 TỈNH NINH BÌNH Môn: Tin học - Vòng 2 ĐỀ THI CHÍNH THỨC Thời gian làm bài: 180 phút (không kể thời gian giao đề) (Đề thi gồm 03 bài trong 02 trang) Tổng quan đề thi: Chương trình Input Thời gian Bài Output chạy 1- Đoạn con SUBSEQ.PAS SUBSEQ.INP SUBSEQ.OUT 1giây/test 2- Đường đi ROBOT.PAS ROBOT.INP ROBOT.OUT 1giây/test 3- Truyền tin TT.PAS TT.INP TT.OUT 1giây/test Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. Bài 1 (7,0 điểm): Đoạn con Cho dãy số nguyên a1, a2,..., aN (|ai| < 109, N < 105). Một tập hợp khác rỗng các số hạng liên tiếp {ai, ai+1,..., ak} (i  k) gọi là một đoạn con của dãy đó. Với mỗi đoạn con ta tính tổng tất cả các số hạng của nó. Yêu cầu: Tìm giá trị lớn nhất trong số các tổng của các đoạn con của dãy đã cho. Dữ liệu vào: cho trong file SUBSEQ.INP: Dòng đầu chứa số N, dòng thứ i trong N dòng tiếp theo chứa số ai. Dữ liệu ra: Ghi ra file SUBSEQ.OUT một số nguyên là giá trị tổng đoạn con lớn nhất tìm được. Ví dụ: SUBSEQ.OUT SUBSEQ.INP 7 8 1 -2 (Giải thích: -1 đoạn con tổng 4 lớn nhất là: -1 4 – 1 + 5 = 8)
5 -2 (60% số test có N < 3000) BÀI 2 (7,0 điểm): Đường đi Cho một bảng vuông kích thước N*N (với 2 < N < 100). Mỗi ô trong bảng ghi một số nguyên thuộc khoảng (-32000; 32000). Yêu cầu: Tìm đường đi của robot từ ô góc trên trái (dòng 1 cột 1) xuống ô góc dưới phải (dòng n cột n) của bảng sao cho tổng các số trên đường đi là nhỏ nhất. Biết rằng mỗi bước từ một ô Robot chỉ có thể đi sang ô kề cạnh bên phải hoặc bên dưới so với ô nó đang đứng. Dữ liệu vào: Cho trong file Robot.inp - Dòng đầu ghi giá trị số n. - Dòng thứ i trong n dòng tiếp theo ghi n số trên dòng i của bảng theo thứ tự từ trái qua phải. Dữ liệu ra: Ghi ra file Robot.out một số nguyên là tổng giá trị đường đi nhỏ nhất tìm được. Ví dụ: ROBOT.INP ROBOT.OUT 3 25 12 11 15 4 6 9 (Giải thích: đường đi có tổng bé nhất: -12 25 -4 (1,1) => (2,1) => (3,1) => (3,2) => (3,3) có tổng: 12 + 4 – 12 + 25 – 4 = 25) (60% số test có N < 13) Bài 3 (6,0 điểm): Truyền tin Thời cổ đại, một trong những phương tiện truyền tin hiệu quả sử dụng chim đưa thư. Một vương quốc có N đơn vị hành chính đánh số từ 1 đến N( kinh thành được đánh số là 1). Hệ thống truyền tin được Quốc vương xây dựng như sau: Mỗi đơn vị hành chính có danh sách một số đơn vị khác để khi nhận được một thông tin (từ kinh thành hay từ các đơn vị khác truyền đến) thì sẽ lập tức dùng chim đưa thư truyền tin đến các đơn vị trong
danh sách đó. Khi có một mệnh lệnh cần ban hành nó sẽ được truyền đi từ kinh thành và hệ thống đã xây dựng đảm bảo thông tin đến được với mọi đơn vị hành chính. Sau một thời gian hoạt động, Quốc vương muốn đánh giá hiệu quả của hệ thống truyền tin. Vì thế ngài muốn các cơ quan phụ trách hệ thống này cho biết: mỗi đơn vị hành chính nhận được thông tin lần đầu tiên sau thời gian bao lâu khi nó được ban hành từ kinh thành? Một vấn đề thực sự không đơn giản! Yêu cầu: Cho biết hệ thống truyền tin, thời gian truyền tin giữa hai đơn vị trong hệ thống. Xác định thời gian nhận được thông tin sớm nhất của mỗi đơn vị hành chính tính từ khi thông tin được truyền đi từ kinh thành. Dữ liệu vào: Cho trong file TT.INP: - Dòng đầu ghi hai số N và M (N
Hä vµ tªn thÝ sinh...................................... Sè b¸o danh:......................................................... Ch÷ kÝ cña gi¸m thÞ 1................................ Ch÷ kÝ cña gi¸m thÞ 2............................................ const fi = 'subseq.inp'; fo = 'subseq.out'; nmax = 100000; var n:longint; S:array[0..nmax] of int64; kq:int64; procedure nhapdulieu; var f:text; i,a:longint; begin s[0]:=0; assign(f,fi); reset(f); readln(f,n); for i:= 1 to n do begin readln(f,a); s[i]:=s[i-1]+a; end; close(f); end; procedure xuly; var i,j:longint;
max:int64; f:text; begin max:=s[n]; kq:=-200000000000000; for i:= n-1 downto 0 do begin if kqmax then max:=s[i]; end; assign(f,fo); rewrite(f); writeln(f,kq); close(f); end; begin nhapdulieu; xuly; end. 7 -1 -2 -1 -4 -1 -5 -2 Const fi='robot.inp'; fo='robot.out'; Var A:array[1..100,1..100] of integer; T:array[1..100,1..100] of longint; n,m,i,j:integer; F,F1:text; Procedure Readfile; Begin Assign(f,fi); reset(f); readln(f,n); For i:=1 to n do Begin For j:=1 to n do
read(f,a[i,j]); readln(f); End; close(f); End; Procedure Quyhoachdong; Begin T[1,1]:=a[1,1]; For i:=2 to n do {tinh cho dong o bien} Begin T[i,1]:=T[i-1,1]+a[i,1]; T[1,i]:=T[1,i-1]+a[1,i]; End; For i:=2 to n do {Tinh ben trong} For j:=2 to n do If T[i,j-1] < T[i-1,j] then T[i,j]:=T[i,j-1]+a[i,j] else T[i,j]:=T[i-1,j]+a[i,j]; End; BEGIN readfile; fillchar(T,sizeof(T),0); Quyhoachdong; assign(f,fo); rewrite(f); Write(f,T[n,n]); close(f); END. const fi = 'tt.inp'; fo = 'tt.out'; mmax = 100000; nmax = 10001; vc = 2000000000; var m,n : longint; tro,cs : array[0..nmax]of longint;
ds,tg : array[1..2*mmax] of integer; vtri : array[1..nmax] of integer; heap : array[1..nmax] of integer; d : array[1..nmax] of longint; procedure nhapdulieu; var i,ii,j,t:longint; f:text; begin assign(f,fi); reset(f); fillchar(tro,sizeof(tro),0); readln(f,n,m); for i:=1 to m do begin readln(f,j); inc(tro[j]); end; close(f); for i:=2 to n do tro[i]:=tro[i]+tro[i-1]; cs:=tro; assign(f,fi); reset(f); readln(f,n,m); for ii:=1 to m do begin readln(f,i,j,t); ds[tro[i]]:=j; tg[tro[i]]:=t; dec(tro[i]); end; close(f); end; procedure UpHeap(i,k:integer); var j,u,khoa:longint;
begin khoa:=d[heap[i]]; u:=heap[i]; while i shl 1
heap[i]:=u; vtri[u]:=i; end; procedure Ijk_heap; var i,j,sl,u,v:longint; begin for i:=1 to n do begin d[i]:=vc; vtri[i]:=0; end; heap[1]:=1; vtri[1]:=1; sl:=1; d[1]:=0; for i:=1 to n-1 do begin u := heap[1]; if sl>1 then begin heap[1]:=heap[sl]; vtri[heap[1]]:=1; Upheap(1,sl-1); end; dec(sl); for v:= cs[u-1]+1 to cs[u] do if d[ds[v]]>d[u]+tg[v] then begin d[ds[v]]:= d[u] + tg[v]; if vtri[ds[v]]=0 then begin inc(sl); heap[sl]:=ds[v]; vtri[ds[v]]:=sl; end; Downheap(vtri[ds[v]]); end; end;
end; procedure inkq; var i:longint; g:text; begin assign(g,fo); rewrite(g); for i:=1 to n do writeln(g,d[i]); close(g); end; begin nhapdulieu; Ijk_heap; inkq; end.