Sở giáo dục - đào tạo thừa thiên huế
Tr ờng thpt tam giang
Kỳ thi chọn hsg thpt năm 2006 - 2007
đề thi môn: tin học lớp 12
(Thời gian: 150 phút, không kể thời gian giao đề)
thí sinh lập trình bằng pascal giải hai bài toán sau:
Bài 1: phân phối hàng.
Có N công trờng cần vật liệu thi công. Công trờng i cần cung cấp D[i]
đơn vị hàng. Hàng đợc cung cấp từ hai kho A và B. Cớc vận chuyển một đơn vị
hàng từ kho A đến công trờng i là A[i]. Cớc vận chuyển một đơn vị hàng từ kho
B đến công trờng i là B[i]. Biết rằng kho A có R đơn vị hàng và tổng số hàng
của hai kho đủ cung cấp cho N công trờng.
Yêu cầu:
Hãy phân phối hàng từ hai kho đến các công trờng sao cho tổng cớc phí
vận chuyển là ít nhất.
Dữ liệu vào:
File HANG.INP có cấu trúc nh sau:
Dòng 1:
Ghi 2 số N, R (N < 10000)
Dòng 2:
Ghi N số D[1], D[2], ... , D[N]
Dòng 3:
Ghi N số A[1], A[2], ... , A[N]
Dòng 4:
Ghi N số B[1], B[2], ... , B[N]
Dữ liệu ra:
File HANG.OUT có cấu trúc nh sau:
Dòng 1:
Ghi một số nguyên dơng là tổng chi phí vận chuyển ít nhất.
Dòng 2:
Ghi N số nguyên không âm tơng ứng số đơn vị hàng mà kho A cung cấp

File BALANCE.OUT có cấu trúc nh sau:
- Dòng đầu là số thứ tự của nút có cân bằng nhỏ nhất.
- Dòng tiếp là cân bằng của nút đó
Ví dụ:
BALANCE.INP BALANCE.OUT
7
2 6
1 2
1 4
4 5
3 7
3 1
1
2
------------------------- Hết -------------------------
2 1 3
6 4 7
5
- Giám thị không giải thích gì thêm.
- Các file nguồn đặt tên tơng ứng là bai1.pas, bai2.pas
ĐáP áN
Bài 1.
Program bai1;
Const fi=hang.inp;
fo=hang.out;
Type mang=array[0..10000] of integer;
Var s:real;
n,r,k,w,x,y:integer;
a,b,cs:mang;
d:^mang;

tg:=cs[i];
cs[i]:=cs[j];
cs[j]:=tg;
inc(i);
dec(j);
end;
until i>j;
if l<j then Qsort(l,j);
if i<r then Qsort(i,r);
End;
Procedure TimK;
Var i,t:integer;
Begin
s:=0;
t:=0;
k:=0;
while t+d^[cs[k]]<r do
begin
inc(k);
t:=t+d^[cs[k]];
s:=s+a[cs[k]]*d^[cs[k]];
a[cs[k]:=-a[cs[k]];
end;
x:=r-t;
y:=d^[cs[k+1]]-(r-t);
s:=s+a[cs[k+1]]*x+b[cs[k+1]]*y;
for i:=k+2 to n do
s:=s+b[cs[i]]*d^[cs[i]];
w:=cs[k+1];
End;

fo= ‘BALANCE.OUT’;
max=20000;
Type m1=array[0..max+1] of integer;
Var n:integer;
a:m1;
d,c,tr,t:^m1;
f:text;
Procedure Nhap;
Var i:integer;
Begin
new(d);
new(c);
new(tr);
new(t);
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n-1 do readln(f,d^[i],c^[i]);
close(f);
End;
Procedure Xuat;
Var i,min:integer;
Begin
dispose(d);
dispose(c);
dispose(tr);
dispose(t);
min:=1;
for i:=2 to n do
if a[i]<a[min] then min:=i;