Kỳ thi chọn học sinh giỏi cấp tỉnh lớp 12 năm học 2012 - 2013 môn thi: tin học

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
1 4 3 1 2 1 6 5 1 4 1	3 1 2
6
5 1
1 4 1
5 6
1 2 5 2 1	0
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
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	2
==HẾT==
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(x1, 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
0 0
1 0
0 1
0.5
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.
Ví dụ:
NOUCAMP.INP
NOUCAMP.OUT
16 10
2 3 6 7 8 9 10 12 15 16 
1 4 5 11 13 14
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 bi, 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
1 5
5 7
6 4
3 6
2 5
3
2 3 5
==HẾT==
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;
 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<m )and (j<=n) do
 begin
 t:=t+a[j];
 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);
 close(f);
end;
Begin
doc; xl;
xuatstp;
End.
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';
 	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;
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 then
 begin
 { y := a[i]; a[i] := a[j]; a[j] := y;}
 Doi1(a[i],a[j]); Doi1(b[i],b[j]); Doi(s[i],s[j]); Doi1(vt[i],vt[j]);
 i := i + 1; j := j - 1;
 end;
 until 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]<b[i] then Doi1(a[i],b[i]);
 End;
 Close(f);
 Fillchar(s,sizeof(s),0);
 For i:=1 to n do
 S[i]:=longint(a[i])*Longint(b[i]);
 Sort(1,n);
End;
Function Bao(i,j:Integer):boolean;
Begin
 Bao:= (a[j]>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<sl[i] then
 Begin
 Maxx:=sl[i]; V:=i;
 End;
 Assign(f,fo);
 Rewrite(f);
 Writeln(f,maxx);
 For i:=1 to maxx do
 Begin
 Sl[i]:=v; V:=tr[v];
 End;
 For i:= 1 to maxx do Writeln(f,Vt[sl[i]],' ');
 Close(f);
End;
Begin
 Init; Qhd; 
End.