Đề thi HSG lớp 12 năm 2013 môn Tin - Sở GD&ĐT tỉnh Quảng Bình

Chia sẻ: Phung Tuyet | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

428
lượt xem 44
download

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

Cùng tham khảo đề thi học sinh giỏi môn Tin lớp 12 năm 2013 giúp các em ôn tập lại các kiến thức đã học, đánh giá năng lực làm bài của mình và chuẩn bị kì thi học sinh giỏi được tốt hơn với số điểm cao như mong muốn.

Chủ đề:

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

Lưu

Nội dung Text: Đề thi HSG lớp 12 năm 2013 môn Tin - Sở GD&ĐT tỉnh Quảng Bình

Së Gd&§t kú thi CHäN häc sinh giái cÊp tØnh líp 12 thpt Qu¶ng b×nh n¨m häc 2012 - 2013 M«n thi: tin häc - Vßng I §Ò thi chÝnh thøc (Khãa thi ngµy 11 th¸ng 10 n¨m 2012) Sè B¸o Danh: ................ Thêi gian lµm bµi: 180 phót (kh«ng kÓ thêi gian giao ®Ò) ĐỀ RA Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau: Câu 1: (3,0 điểm) Sắp xếp xâu. SAPXAU.PAS Người ta định nghĩa: Từ là một nhóm ký tự đứng liền nhau. Cho một xâu St gồm các ký tự lấy từ tập ‘a’ .. ‘z’ và dấu cách. Xâu không quá 20 từ, mỗi từ dài không quá 10 ký tự. Yêu cầu: Sắp xếp các từ của xâu ký tự theo thứ tự không giảm của độ dài các từ trong xâu St. Dữ liệu vào: Cho trong file văn bản SAPXAU.INP, có cấu trúc: - Dòng 1: Ghi một xâu ký tự St (có ít nhất 1 từ). Dữ liệu ra: Ghi ra file văn bản SAPXAU.OUT, theo cấu trúc: - Dòng 1: Ghi các từ của xâu ký tự sau khi được sắp xếp. Các từ được ghi cách nhau đúng một dấu cách. Ví dụ: SAPXAU.INP SAPXAU.OUT acb abcde abcd abc acb abc abcd abcde Câu 2: (3,5 điểm) Dãy con liên tiếp. DAYCON.PAS Cho dãy số nguyên dương gồm N phần tử A1, A2,…, An. Yêu cầu: Hãy liệt kê tất cả các dãy con gồm các phần tử đứng liên tiếp của dãy trên sao cho tổng giá trị các phần tử của dãy con đó bằng M. Dữ liệu vào: Cho trong file văn bản DAYCON.INP, có cấu trúc như sau: - Dòng 1: Ghi 2 số nguyên dương N và M. Hai số được ghi cách nhau ít nhất một dấu cách. (1  N  1000; 1  M  32000) - Dòng 2: Ghi N số nguyên dương Ai. Các số được ghi cách nhau ít nhất một dấu cách. (1  Ai  10000 ) Dữ liệu ra: Ghi ra file văn bản DAYCON.OUT, gồm nhiều dòng. Mỗi dòng ghi một dãy con tìm được. Các dãy con được ghi theo thứ tự xuất hiện của nó trên dãy ban đầu. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Nếu không tìm được dãy con thỏa mãn điều kiện thì ghi ra file một số: 0. Ví dụ: DAYCON.INP DAYCON.OUT 11 6 3 1 2 1 4 3 1 2 1 6 5 1 4 1 6 5 1 1 4 1 5 6 0 1 2 5 2 1 1
Câu 3: (3,5 điểm) Đếm nhóm bạn trong Hội trại NHOMBAN.PAS Trong một Hội trại hè do Tỉnh Đoàn tổ chức, có N học sinh tham gia, trong đó, có một số học sinh quen nhau. Một số học sinh được gọi là cùng 1 nhóm bạn, nếu bất kì một học sinh nào thuộc nhóm đều có quen ít nhất 1 học sinh khác trong cùng nhóm đó. Yêu cầu: Hãy đếm xem có bao nhiêu nhóm bạn trong N học sinh tham gia Hội trại. Dữ liệu vào: Cho trong file văn bản NHOMBAN.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, là số lượng học sinh tham gia Hội trại. (1 ≤ N ≤ 100). - Trong N dòng tiếp theo: Mỗi dòng ghi N số nguyên dương a[i,j] với ý nghĩa: a[i,j] = 1 nếu học sinh i quen học sinh j (với i ≠j). a[i,j] = 0 nếu học sinh i không quen học sinh j (với i ≠j). a[i,i] = 1 (học sinh i được xem là quen bản thân nó). Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản NHOMBAN.OUT, theo cấu trúc như sau: - Dòng 1: Ghi số nguyên dương K, là số lượng nhóm bạn tìm được trong N học sinh tham gia Hội trại. Ví dụ: NHOMBAN.INP NHOMBAN.OUT 5 2 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 ==HẾT== 2
Së GD&§T kú thi CHäN häc sinh giái cÊp tØnh líp 12 THPT Qu¶ng b×nh n¨m häc 2012 - 2013 M«n thi: tin häc - Vßng i híng dÉn chÊm I. Phương pháp: - Giám khảo tạo bộ dữ liệu vào, tính toán kết quả. Thực hiện chương trình của học sinh và so sánh kết quả. - Giám khảo có thể sử dụng chương trình gợi ý dưới đây để tính toán kết quả của dữ liệu vào. - Chương trình học sinh đúng một bộ test, giám khảo cho 0,5 điểm. Như vậy, nếu một câu có 3 điểm thì giám khảo phải tạo 6 bộ test. - Với mỗi câu, giám khảo phải tạo được ít nhất một bộ test có không gian dữ liệu lớn. - Riêng Câu 1, thứ tự sắp xếp của HS có thể khác với đáp án. Nếu kết quả của học sinh khác đáp án nhưng vẫn đúng thì giám khảo vẫn cho điểm tối đa. II. Chương trình gợi ý: Câu 1: (3,0 điểm) Sắp xếp xâu program sap; const f1='sapxau.inp'; f2='sapxau.out'; type mm=array[1..20] of string; var a:mm; s,st,tg:string; d:integer; f:text; procedure doc; begin assign(f,f1); reset(f); readln(f,s); close(f); end; procedure xl; var x,j,i:integer; n:byte; begin n:=length(s); while s[1]=' ' do delete(s,1,1); while s[n]=' ' do delete(s,n,1); x:=pos(' ',s); while x>0 do begin delete(s,x,1); x:=pos(' ',s); end; s:=s+' '; for i:=1 to 20 do a[i]:=''; i:=0; while s'' do begin i:=i+1; a[i]:=copy(s,1,pos(' ',s)-1); delete(s,1,pos(' ',s)); end; 3
d:=i; { for j:=1 to d do begin i:=1;st:=''; while (s[i]' ')do begin st:=st+s[i]; i:=i+1; end; delete(s,1,i); a[j]:=a[j]+st; end;} for i:=1 to d-1 do for j:=i+1 to d do if length(a[i])>length(a[j]) then begin tg:=a[i];a[i]:=a[j];a[j]:=tg; end; end; procedure xuat; var i:integer; begin assign(f,f2); rewrite(f); for i:=1 to d do write(f,a[i],' '); close(f); end; begin doc;xl;xuat; end. Câu 2: (3,5 điểm) Dãy con liên tiếp program day_con; const fi='daycon.inp'; f0='daycon.out'; type mm=array[1..10000] of integer; var f:text; a:mm; n,m:integer; procedure doc; var i:integer ; begin assign(f,fi); reset(f); read(f,n,m); for i:=1 to n do read(f,a[i]); close(f); end; procedure xuli; var i,j,l:integer; t:longint; kt:boolean; begin assign(f,f0); rewrite(f); kt:=false; for i:=1 to n do begin j:=i; t:=0; while (t
j:=j+1; end; if t=m then begin kt:=true; for l:=i to j-1 do write(f,a[l],' '); writeln(f); end; end; if kt=false then write(f,0); close(f); end; begin doc; xuli; end. Câu 3: (3,5 điểm) Đếm nhóm bạn trong Hội trại const fi='nhomban.inp'; fo='nhomban.out'; maxn=100; type mhc=array[1..maxn,1..maxn] of byte; mmc=array[1..maxn] of byte; var a:mhc; b:mmc; n,stp:integer; f:text; Procedure doc; var i,j:integer; 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 xl; var i,j,k:integer; Begin for i:=1 to n do b[i]:=n+1; stp:=0; for k:=1 to n do begin if b[k]=n+1 then begin stp:=stp+1; b[k]:=stp; end; for i:=1 to n do begin if b[i] = stp then for j:=1 to n do if (a[i,j]=1) and (b[j]=n+1) then b[j]:=stp; end; end; end; procedure xuatstp; begin assign(f,fo); rewrite(f); writeln(f,stp); 5
close(f); end; Begin doc; xl; xuatstp; End. 6
Së Gd&§t kú thi CHäN häc sinh giái cÊp tØnh líp 12 thpt Qu¶ng b×nh n¨m häc 2012 - 2013 M«n thi: tin häc - Vßng II §Ò thi chÝnh thøc (Khãa thi ngµy 11 th¸ng 10 n¨m 2012) Sè B¸o Danh: ................ Thêi gian lµm bµi: 180 phót (kh«ng kÓ thêi gian giao ®Ò) ĐỀ RA Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau: Câu 1: (3,0 điểm) Tính diện tích tam giác. DT.PAS. Trong hệ trục tọa độ Decac, cho ba điểm không thẳng hàng A, B, C có tọa độ: A(x 1, y1); B(x2, y2); C(x3, y3). Yêu cầu: Tính diện tích tam giác ABC. Dữ liệu vào: Cho trong file văn bản DT.INP, có cấu trúc 3 dòng, mỗi dòng chứa hai số nguyên xi yi, là tọa độ của một đỉnh của tam giác ABC. Các số được ghi cách nhau ít nhất một dấu cách. (-2000 ≤ xi, yi ≤ 2000) Dữ liệu ra: Ghi ra file văn bản DT.OUT, theo cấu trúc: - Dòng 1: Ghi diện tích tam giác tìm được. Làm tròn kết quả đến một chữ số sau dấu ngăn cách thập phân. Ví dụ: DT.INP DT.OUT 00 0.5 10 01 Câu 2: (3,5 điểm) Đặt vé vào sân NouCamp NOUCAMP.PAS NouCamp là một sân bóng lớn. Sân có N ghế ngồi, các ghế được đánh số thứ tự từ 1 đến N. Tối nay, sân NouCamp sẽ diễn ra trận đấu giữa hai đội bóng lớn của thế giới: Barcelona và Real Madrid. Hiện nay, một số ghế trên sân đã được khán giả đặt mua làm chỗ ngồi. Yêu cầu: Hãy kiểm tra xem trên sân còn những ghế nào chưa được mua vé đặt chỗ. Dữ liệu vào: Cho trong file văn bản NOUCAMP.INP, có cấu trúc như sau: - Dòng 1: Ghi hai số nguyên dương N M. Trong đó: N là số lượng ghế có trong sân. M là số lượng ghế đã được khán giả mua vé đặt chỗ. Hai số được ghi cách nhau ít nhất một dấu cách. (N chia hết cho 8; 1 ≤ N ≤ 400000; 1 ≤ M ≤ N). - Dòng 2: Ghi M số nguyên dương a1, a2, …, am, là chỉ số của M ghế đã được khán giả mua vé đặt chỗ. Các số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản NOUCAMP.OUT, theo cấu trúc như sau: - Dòng 1: Ghi K số nguyên dương b1, b2, …, bk, là chỉ số của các ghế trên sân chưa được mua vé đặt chỗ (K = N-M). Các số được ghi theo thứ tự tăng dần và cách nhau ít nhất một dấu cách. 1
Ví dụ: NOUCAMP.INP NOUCAMP.OUT 16 10 1 4 5 11 13 14 2 3 6 7 8 9 10 12 15 16 Câu 3: (3,5 điểm) Xếp hộp lồng nhau XEPHOP.PAS Bé Ri tuy còn nhỏ nhưng là một cô bé rất xinh xắn và chăm chỉ. Mẹ bé Ri là chủ một cửa hàng. Hàng ngày, cửa hàng của mẹ loại ra rất nhiều hộp giấy hình hộp chữ nhật. Bé Ri thường giúp mẹ xếp những hộp giấy này lồng vào nhau cho gọn. Giả sử có N hộp giấy, các hộp được đánh số từ 1 đến N. Với mỗi hộp giấy, bé Ri biết được chính xác độ dài hai cạnh đáy của hộp là a và b. Yêu cầu: Hãy giúp bé Ri xếp các hộp sao cho số lượng các hộp lồng vào nhau là lớn nhất. Dữ liệu vào: Cho trong file văn bản XEPHOP.INP, có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N, là số lượng hộp giấy. (1 ≤ N ≤ 1000) - N dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương ai b i, là độ dài hai cạnh đáy của hộp giấy thứ i. (1 ≤ ai, bi ≤ 32767) Dữ liệu ra: Ghi ra file văn bản XEPHOP.OUT theo cấu trúc như sau: - Dòng 1: Ghi số nguyên dương M là số lượng các hộp giấy lồng nhau tìm được. - Dòng 2: Ghi M số nguyên dương, là chỉ số của M hộp giấy theo thứ tự từ ngoài vào trong của một cách xếp hộp. Ví dụ: XEPHOP.INP XEPHOP.OUT 5 3 1 5 2 3 5 5 7 6 4 3 6 2 5 ==HẾT== 2
Së GD&§T kú thi CHäN häc sinh giái cÊp tØnh líp 12 THPT Qu¶ng b×nh n¨m häc 2012 - 2013 M«n thi: tin häc - Vßng iI híng dÉn chÊm I. Phương pháp: - Giám khảo tạo bộ dữ liệu vào, tính toán kết quả. Thực hiện chương trình của học sinh và so sánh kết quả. - Giám khảo có thể sử dụng chương trình gợi ý dưới đây để tính toán kết quả của dữ liệu vào. - Chương trình học sinh đúng một bộ test, giám khảo cho 0,5 điểm. Như vậy, nếu một câu có 3 điểm thì giám khảo phải tạo 6 bộ test. - Với mỗi câu, giám khảo phải tạo được ít nhất một bộ test có không gian dữ liệu lớn. - Riêng Câu 3, chỉ số các hộp được chọn của HS có thể khác với đáp án. Nếu kết quả của học sinh khác đáp án nhưng vẫn đúng thì giám khảo vẫn cho điểm tối đa. II. Chương trình gợi ý: Câu 1: (3,0 điểm) Tính diện tích tam giác {$r+} const fi='dt.inp'; fo='dt.out'; type mm=array [1..4] of integer; var a,b:mm; f:text; s:real; procedure nhap; var i:integer; begin assign(f,fi); reset(f); for i:=1 to 3 do readln(f,a[i],b[i]); close(f); end; procedure xuly; var i:integer; T1,T2:LONGINT; begin a[4]:=a[1]; b[4]:=b[1]; s:=0; for i:=1 to 3 do begin t1:=b[i+1]+b[i]; t2:=a[i+1]-a[i]; s:=s+(t1*t2)/2; end; end; procedure xuat; begin assign(f,fo); rewrite(f); write(f,abs(s):0:1); close(f); end; begin nhap; xuly; xuat; end. Câu 2: (3,5 điểm) Đặt vé vào sân NouCamp Const fi='noucamp.in1'; 3
fg='noucamp.out'; maxn=51000; type mmc=array[1..maxn] of byte; var a:mmc; ti,n,m:longint; procedure xl; var f:text; i,x:longint; by,bi:word; begin fillchar(a,sizeof(a),0); assign(f,fi);reset(f); readln(f,n,m); for i:=1 to m do begin read(f,x); by:=(x div 8)+1; bi:= x mod 8; if bi=0 then begin bi:=8; by:=by-1; end; a[by]:=a[by] or (1 shl (bi-1)); end; close(f); end; procedure xuat; var f:text; i,j:longint; begin assign(f,fg);rewrite(f); {writeln(f,n-m);} for i:= 1 to n div 8 do for j:=1 to 8 do if ((a[i] shr (j-1)) and 1)=0 then write(f,(i-1)*8+j,' '); close(f); end; begin xl; xuat; end. Câu 3: (3,5 điểm) Xếp hộp lồng nhau {$R+,Q+} {$M 63840,0,655360} Const Fi='xephop.in1'; Fo='xephop.out'; Type Mang=Array[0..5000] of integer; Var A,b,vt:Mang; F:Text; M,n:integer; Function Max(a,b:Integer):integer; Begin Max:=a; If b>a then Max:=b; End; Procedure Doi(Var A,b:Longint); Var T:Longint; Begin T:=a; A:=b; B:=t; End; Procedure Doi1(Var A,b:integer); Var T:integer; Begin T:=a; A:=b; B:=t; End; Procedure Init; Var S:Array[0..5000] Of Longint; I,j:Integer; procedure Sort(l, r: Integer); var i, j, x, y: Longint; 4
begin i := l; j := r; x := s[(l+r) DIV 2]; repeat while s[i] < x do i := i + 1; while x < s[j] do j := j - 1; if i j; if l < j then Sort(l, j); if i < r then Sort(i, r); end; Begin Assign(f,fi); Reset(f); Readln(f,n); For i:=1 to n do vt[i]:=i; For i:=1 to n do Begin Readln(f,a[i],b[i]); If A[i]a[i]) And (b[j]>b[i]); End; Procedure Qhd; Var I,j,maxx,v:Integer; Tr,sl:Array[0..5000] Of Integer; Begin For i:=1 to n do sl[i]:=1; For i:=2 to n do For j:=i-1 downto 1 do If sl[j]+1>sl[i] then if Bao(j,i) then Begin Tr[i]:=j; Sl[i]:=sl[j]+1; End; Maxx:=1; V:=1; For i:=1 to n do If Maxx
End; Begin Init; Qhd; End. 6