Đề thi chọn học sinh giỏi lớp 12 năm học 2010 - 2011 môn: tin học

SỞ GIÁO DỤC VÀ ĐÀO TẠO
ĐỀ THI CHÍNH THỨC
TỈNH NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT
NĂM HỌC 2010 - 2011
Môn: Tin học - Vòng 2
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:
Bài
Chương trình
Input
Output
Thời gian 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.INP
SUBSEQ.OUT
7 
 1 
 -2 
 -1 
 4 
-1 
 5
-2
8
(Giải thích: đoạn con tổng lớn nhất là:
4 – 1 + 5 = 8)
(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
12 11 15
4 6 9
-12 25 -4
25
(Giải thích: đường đi có tổng bé nhất: 
(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<10000, M<100000). 
 - M dòng sau, mỗi dòng chứa ba số nguyên dương i j t với ý nghĩa: đơn vị j có trong danh 
sách truyền tin của đơn vị i và thời gian truyền tin từ i đến j là t (t < 104).
Dữ liệu ra: Ghi ra file TT.OUT :
 N số nguyên dương, trên dòng thứ k là thời gian để lần đầu tiên đơn vị thứ k nhận được 
thông tin.
Ví dụ: 
 TT.INP
TT.OUT
5 7
1 2 3
1 3 1
2 5 6
1 5 7
3 2 1
3 4 2
4 5 2
0
2
1
3
5
(60% test có M < 1000)
 ---------------------Hết---------------------
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 kq<max-s[i] then kq:=max-s[i];
 if s[i]>max 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 <= k do
 begin
 j:= i shl 1;
 if (j<k)and(d[heap[j+1]]<d[heap[j]]) then inc(j);
 if khoa>d[heap[j]] then
 begin
 heap[i]:=heap[j];
 vtri[heap[i]]:=i;
 i:=j;
 end
 else break;
 end;
 heap[i]:=u;
 vtri[u]:=i;
end;
procedure Downheap(i:integer);
var j,u,khoa:longint;
begin
 khoa:=d[heap[i]];
 u:=heap[i];
 while i shr 1 >=1 do
 begin
 j:= i shr 1;
 if khoa<d[heap[j]] then
 begin
 heap[i]:=heap[j];
 vtri[heap[i]]:=i;
 i:=j;
 end
 else break;
 end;
 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.