Hội thi giáo viấn dạy giỏi bậc THPT chu kỳ 2011 – 2015 môn thi: Tin học (phần lập trình)

SỞ GD&ĐT NGHỆ AN
Đề thi chính thức
(Đề thi gồm 02 trang)
 HỘI THI GIÁO VIấN DẠY GIỎI BẬC THPT
CHU KỲ 2011 – 2015
Mụn thi: TIN HỌC (Phần lập trỡnh)
Thời gian làm bài 120 phỳt ( không kể thời gian giao đề)
Chú ý: Đây không phải là đáp án chính thức. Và chỉ là phần lập trình
Mà do không thấy đáp án của Sở ở đâu nên rảnh rổi ngồi code cho vui. Nên có thể có nhiều sai sót.
Quý vị cũng có thể có nhiều cách giải hay hơn. Cảm ơn!
Bài 1 (5,5 điểm). TRẠM TIẾP NƯỚC NGỌT
 	Tại một khu công nghiệp có N chung cư (1<=N<=100) và được gắn số hiệu lần lượt theo thứ tự từ 1, 2, ..., N. Hàng ngày, công ty cấp thoát nước vận chuyển cấp cho mỗi chung cư một xe nước.
Yêu cầu: Tìm cho công ty cấp thoát nước một địa điểm đặt trạm tiếp nước cho N chung cư này thoả mãn các yêu cầu sau: 
Tại một chung cư nào đó. Khi vận chuyển nước từ trạm đến một chung cư nào đó thì không được đi qua một chung cư trung gian nào. 
Tổng chi phí vận chuyển là nhỏ nhất.
Dữ liệu: Vào cho từ file văn bản NUOC.INP có cấu trúc như sau:
Dòng đầu tiên ghi số N
Các dòng tiếp theo ghi 3 số nguyên dương X, Y, CXY có nghĩa là chi phí vận chuyển một xe nước từ chung cư có số hiệu X đến chung cư có số hiệu Y là CXY (1<= X, Y<= N, 0 < CXY <= 32000) (các số trên một dòng ghi cách nhau một dấu cách) 
Kết quả: Ghi ra file văn bản NUOC.OUT như sau:
Dòng đầu tiên ghi số hiệu của chung cư đặt trạm tiếp nước (nếu có nhiều địa điểm đặt trạm, thì chọn chung cư có số hiệu nhỏ nhất)
Dòng thứ hai ghi tổng chi phí vận chuyển nước đến N chung cư của khu công nghiệp này.
Ví dụ:
NUOC.INP
NUOC.OUT
5
1 2 12
1 3 10
1 4 7
1 5 5
2 3 11
2 4 8
2 5 7
3 4 3
3 5 9
4 5 7
4
25
Ý tưởng: Chi phí vận chuyển nước từ khu X sang khu Y cũng bằng chi phí chuyển từ khu Y sang khu X. 
Vì thế ta dựa vào dữ liệu vào để tạo bảng tra cho chi phí vận chuyển từ khu bất kỳ qua tất cả các khu còn lại.
Rồi sau đó tìm khi có tổng chi phí nhỏ nhất.
Program TramTiepNuoc;
Var A:array[1..100] of longint;
 n:byte;
Procedure DocFile;
var f:text;
 x,y:byte;
 z:integer;
Begin
 assign(f,'nuoc.inp'); reset(f);
 readln(f,N);
 While not Eof(f) do
 Begin
 readln(f,x,y,z);
 A[x]:=A[x]+z;
 A[y]:=A[y]+z;
 End;
 close(f);
End;
Procedure XuLy;
var f:text;
 min,i:byte;
 Begin
 max:=1;
 for i:=1 to n do
 if A[i]<A[min] then Min:=i;
 assign(f,'Nuoc.OUT'); rewrite(f);
 writeln(f,min);
 write(f,A[min]);
 close(f);
 End;
Begin
 DocFile;
 XuLy;
End.
Bài 2 (5,5 điểm). GHÉP XÂU
Cho 2 xâu ký tự S1, S2. Có thể ghép một số lần liên tiếp xâu S1 để được xâu S2 hay không?
Dữ liệu: Vào từ file văn bản XAU.INP
Dòng đầu tiên ghi xâu S1,
Dòng thứ hai ghi xâu S2.
Kết quả: Ghi vào file văn bản XAU.OUT
Trong trường hợp ghép được, ghi số K là số lần ghép liên tiếp xâu S1 để được xâu S2, trường hợp ngược lại ghi số 0.
Ví dụ
XAU.INP
XAU.OUT
XAU.INP
XAU.OUT
ACM
ACMACMACM
3
MNP
MNPMNPMNPC
0
Ý tưởng: Nếu xâu S2 được ghép từ xâu S1 thì số phần tử của xâu S2 phải chia hết cho số phần tử của xâu s1.
Ta tử tạo xâu S bằng cách ghép liên tiếp xâu S1 lại với nhau (số lần ghép bằng độ dài xâu S2/S1)
Program GhepXau;
var s1,s2:string;
Procedure DocFile;
var f:text;
 Begin
 assign(f,'Xau.inp'); reset(f);
 readln(f,s1);
 readln(f,s2);
 close(f);
 End;
function Ghepduoc(x,y:string):boolean;
var i:byte;
 s:string;
 begin
 s:='';
 for i:=1 to length(y) div length(x) do
 s:=s+x;
 Ghepduoc:=s=y;
 end;
Procedure xuly;
 var f:text;
 Begin
 assign(f,'Xau.out'); rewrite(f);
 if Ghepduoc(s1,s2) then write(f,length(s2) div length(s1))
 else write(f,0);
 close(f);
 End;
Begin
 DocFile;
 Xuly;
End.
Bài 3 (2,5 điểm). PHỦ ĐOẠN THẲNG
Cho đoạn thẳng [a, b] và N đoạn thẳng [a1,b1], [a2,b2], , [aN,bN] trên trục số (1<= N<=100). Đoạn thẳng [a, b] được gọi là bị phủ bởi N đoạn thẳng [a1,b1], [a2,b2], , [aN,bN] nếu [a,b] .
Yêu cầu: Hãy tìm trong N đoạn thẳng [a1,b1], [a2,b2], , [aN,bN] ít nhất K đoạn thẳng, sao cho K đoạn thẳng này phủ đoạn thẳng [a,b].
Dữ liệu: Vào từ file văn bản DOAN_TH.INP:
Dòng đầu tiên ghi 3 số nguyên dương N, a, b là số đoạn thẳng và điểm đầu và điểm cuối của đoạn thẳng [a,b] (-32000 <= a< b <= 32000).
Dòng thứ I trong N dòng tiếp theo ghi 2 số nguyên x, y là điểm đầu và điểm cuối của đoạn thẳng thứ I trong N đoạn thẳng đã cho (-32000 <= x < y <= 32000)
Kết quả: Ghi ra file văn bản DOAN_TH.OUT:
Nếu không tìm được ghi số 0, trong trường hợp ngược lại dòng đầu tiên ghi số K là số đoạn thẳng tìm được, dòng thứ hai ghi K số nguyên dương là chỉ số của các đoạn thẳng phủ đoạn thẳng [a,b].
Cả hai file dữ liệu vào ra, các số trên một dòng ghi cách nhau một dấu cách.
Ví dụ:
DOAN_TH.INP
DOAN_TH.OUT
7 -10 15
-2 1
-11 0
-1 3
-1 8
7 16
0 7
6 20
3
2 4 7
Ý Tưởng: 
Đầu tiên xét từ vị trí a của đoạn [a,b]
B1. Tìm đoạn có bi lớn nhất trong các đoạn có ai nhỏ hơn điểm đang xét à đưa vị trí i vào nghiêm 
B2. Lấy điểm bi mới tìm được để xét tiếp (quay lại B1)
Program Doan_Thang;
Var A,B:array[0..100] of integer;
 C:array[1..100] of byte;
 n:byte;
{Mang A,B đe luu gia tri đau va cuoi cua moi đoan
Mang C: Luu nghiem}
procedure DocFile;
var f:text;
 i:byte;
Begin
 assign(f,'Doan_thang.inp'); reset(f);
 readln(f,N,A[0],B[0]);
 for i:=1 to N do
 readln(f,A[i],B[i]);
 close(f);
End;
{====doan co khoang dai nhat tai diem dang xet}
Function Max(node:integer):byte;
 var csm,i:byte;
 Begin
 csm:=0;
 i:=1;
 while i<=n do
 Begin
 if (A[i]=node) then
 begin
 if csm=0 then csm:=i
 else if B[i]>B[csm] then csm:=i;
 end;
 i:=i+1;
 End;
 Max:=csm;
 End;
Procedure Xuly;
var diem:integer;
 f:text;
 i,vt,dem:byte;
Begin
 assign(f,'Doan_thang.out'); rewrite(f);
 diem:=A[0];
 dem:=0;
 vt:=max(diem);
{Trong khi diem dang xet < diem can phu va van tim duoc doan moi}
 while (diem0) do
 begin
 dem:=dem+1;
 C[dem]:=vt;
 diem:=B[C[dem]];
 vt:=max(diem);
 end;
 writeln(f,dem);
 if dem0 then
 for i:=1 to dem do write(F,C[i],' ');
 close(f);
End;
Begin
 docFile;
 Xuly;
End.
----------------- Hết -----------------