Kỳ thi chọn học sinh giỏi thpt năm 2005 – 2006 đề thi môn: tin học lớp 12 (thời gian: 150 phút, không kể thời gian giao đề)

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 2005 – 2006 đề 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. (4 điểm) 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 cho các công trường 1, 2, , N Ví dụ: HANG.INP HANG.OUT 7 22 3 9 7 6 11 10 8 13 17 20 9 30 10 19 25 16 22 9 30 4 11 835 3 0 7 6 6 0 0 0 9 0 0 5 10 8 Bài 2: CÂN BằNG. (6 điểm) Coi một Cây T với N (1<=N<=20000) nút được đánh số từ 1..N. Hai nút hoặc là nối với nhau bởi một cạnh duy nhất hoặc không nối với nhau. Xoá bất cứ nút nào trong cây sẽ sinh ra một rừng: rừng là một tập hợp một hoặc nhiều cây. Định nghĩa cân bằng của một nút là kích cỡ của cây lớn nhất trong rừng T được tạo bởi bằng cách xoá nút T. 3 1 2 5 4 6 7 Ví dụ: cho một cây: Xoá nút 4 tạo ra hai cây với các nút của chúng là {5} và {1, 2, 3, 6, 7}. Cây lớn hơn trong hai cây có 5 nút, do đó cân bằng của nút 4 là năm Yêu cầu: Dữ liệu vào là một cây. Tính xem nút nào có cân bằng nhỏ nhất, nếu nhiều nút có cùng cân bằng, hãy in ra nút có thứ tự bé nhất. Dữ liệu vào: File BALANCE.INP có cấu trúc như sau: - Dòng đầu: N - Mỗi dòng trong N-1 dòng tiếp theo có hai số chỉ hai điểm của một cạnh trong cây. Không có cạnh nào xuất hiện hai lần trong file, tất cả các cạnh có trong cây đều được thông báo. Dữ liệu ra: 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 Đá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; Procedure Nhap; Var i:integer; f:text; Begin assign(f,fi); reset(f); readln(f,n,r); new(d); fillchar(d^,sizeof(mang),0); for i:=1 to n do Begin cs[i]:=i; read(f,d^[i]); End; for i:=1 to n do read(f, a[i]); for i:=1 to n do read(f, b[i]); close(f); End; {sap xep nhanh theo chi so} Procedure Qsort(l,r:integer); Var i,j,mid,tg:integer; Begin i:=l; j:=r; mid:=a[cs[(l+r) div 2]]-b[cs[(l+r) div 2 ]]; repeat while a[cs[i]]-b[cs[i]]<mid do inc(i); while a[cs[j]]-b[cs[j]]>mid do dec(i); if i<=j then begin 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; Procedure Xuat; Var i:integer; g:text; Begin assign(g, fo); rewrite(g); writeln(g,s:0:0); for i:=1 to w-1 do if a[i]<0 then write(g,d^[i], ‘’) else write(g,0, ‘’); write(g,x, ‘’); for i:=w+1 to n do if a[i]<0 then write(g,d^[i], ‘’) else write(g,0, ‘’); writeln(g); for i:=1 to w-1 do if a[i]>0 then write(g,d^[i], ‘’) else write(g,0, ‘’); write(g,y, ‘’); for i:=w+1 to n do if a[i]>0 then write(g,d^[i], ‘’) else write(g,0, ‘’); close(g); dispose(d); End; BEGIN Nhap; Qsort(1,n); TimK; Xuat; END. Bài 2: Program bai2; Const fi= ‘BALANCE.INP’; 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; assign(f,fo); rewrite(f); writeln(f,min); writeln(f,a[min]); close(f); End; Procedure Xuli; Var i,j,dem,bac,x,y:word; Begin fillchar(a,sizeof(a),0); for i:=1 to n do t^[i]:=1; dem:=0; while dem<n-2 do begin for i:=1 to n-1 do begin x:=d^[i]; y:=c^[i]; if (a[x]-1) and (a[y]-1) then begin inc(a[x]); tr^[x]:=y; inc(a[y]); tr^[y]:=x; end; end; for i:=1 to n-1 do if a[i]=1 then begin a[i]:=-1; inc(t^[tr^[i]],t^[i]); inc(dem); end else if a[i]-1 then a[i]:=0; end; for i:=1 to n do begin if a[i]=0 then tr^[i]:=0; a[i]:=n-t^[i]; end; for i:=1 to n do if t^[i]>a[tr^[i]] then a[tr^[i]]:=t^[i]; End; BEGIN Nhap; Xuli; Xuat; END.