Giải đề GVG Tin Nghệ An

SỞ GD&ĐT NGHỆ AN




(Đề 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] 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