Đáp án của đề thi tin học trẻ THPT tỉnh Quảng Bình lần thứ 10

HỘI THI TIN HỌC TRẺ TỈNH QUẢNG BÌNH LẦN THỨ X ĐỀ THI CHÍNH THỨC - BẢNG C - THPT Ngày thi 15/07/2009. Thời gian làm bài 150 phút Lưu ý: + Đề thi này có 02 trang. + Học sinh tạo một thư mục có tên là số báo danh của thí sinh và lưu bài thi vào thư mục này. + Thí sinh không được sử dụng tài liệu khi làm bài. +Cán bộ coi thi không giải thích gì thêm. 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) Giải nén xâu Tên file chương trình: GNENXAU.PAS Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén văn bản, ta sử dụng một phương pháp đơn giản được mô tả thông qua ví dụ sau: Ví dụ: Với xâu ký tự: ‘aaaabbb’ sẽ được nén lại thành xâu ‘4a3b’. Với xâu ký tự ‘aaab’ sẽ được nén lại thành xâu ‘3ab’. Cho một xâu ký tự St1 gồm các ký tự thuộc tập 'a'..'z'. Gọi St là xâu nén của xâu St1 theo phương pháp được mô tả như trên. Xâu St gồm N (1 N 255) ký tự thuộc tập các ký tự: 'a'..'z', '0'..'9' Yêu cầu: Hãy giải nén xâu St để được xâu gốc St1. Dữ liệu vào: Cho trong file văn bản GNENXAU.INP có cấu trúc như sau: Dòng 1: Ghi xâu ký tự St. Dữ liệu ra: Ghi ra file văn bản GNENXAU.OUT theo cấu trúc như sau: Dòng 1: Ghi xâu St1 là xâu sau khi đã được giải nén. Ví dụ: GNENXAU.INP GNENXAU.OUT 3a5bc aaabbbbbc Câu 2: (3,5 điểm) Thuê vị trí đặt biển quảng cáo. Tên file chương trình: QC.PAS Trung tâm hoạt động Thanh thiếu nhi Bắc Trung Bộ đóng ở một vị trí khá đẹp. Nhiều công ty muốn thuê vị trí để đặt biển quảng cáo. Tại thời điểm hiện tại, chỉ còn duy nhất một chỗ có thể đặt được biển quảng cáo. Giám đốc Trung tâm không đưa ra cụ thể giá thuê mà để khách tự đăng kí. Ông phát cho mỗi khách hàng một phiếu. Khách hàng thứ i phải đăng kí thời điểm bắt đầu thuê (bi), thời gian thuê (ti) và số tiền (mi) mà họ phải trả trong toàn bộ thời gian đó. Đến nay, Giám đốc Trung tâm đã nhận được N phiếu đăng kí thuê (được đánh số từ 1 đến N). Tuy nhiên, ông ta chưa biết nên chọn những khách hàng nào để có được lợi nhuận lớn nhất. Nhân dịp Hội thi Tin học trẻ Quảng Bình lần thứ X, Giám đốc Trung tâm muốn nhờ các thí sinh chọn giúp. Ông hứa sẽ trao thưởng cho thí sinh nào có phương án lựa chọn tốt nhất. Yêu cầu: Hãy giúp Giám đốc Trung tâm xác định cần hợp đồng với những khách hàng nào để số tiền thu được là lớn nhất. Dĩ nhiên, khoảng thời gian thuê của những khách hàng được chọn để làm hợp đồng không được giao nhau (kể cả điểm mút). Dữ liệu vào: Cho trong file văn bản QC.INP có cấu trúc như sau: Dòng 1: Ghi số nguyên dương N là số phiếu đăng kí thuê. (1 ≤ N ≤ 1000) Trong N dòng tiếp theo: Mỗi dòng ghi 3 số nguyên dương bi ti mi lần lượt là thời điểm bắt đầu thuê, thời gian thuê, số tiền phải trả của khách hàng thứ i (i=1..N). Các số được ghi cách nhau ít nhất một dấu cách. (1 ≤ bi ti mi ≤ 32767) Dữ liệu ra: Ghi ra file văn bản QC.OUT theo cấu trúc như sau: Dòng 1: Ghi hai số nguyên dương h và p lần lượt là số lượng hợp đồng phải kí và tổng số tiền thu được từ những hợp đồng này. (Biết rằng: 1 ≤ p ≤ 2100000000) Dòng 2: Ghi chỉ số các khách hàng mà Giám đốc Trung tâm đồng ý cho thuê để thu được số tiền trên. Ví dụ: QC.INP QC.OUT 3 20 40 50 60 20 40 61 30 30 2 80 1 3 Câu 3: (3,5 điểm) Xóa số Tên file chương trình: XOASO.PAS Cho một số nguyên dương N gồm có M chữ số. (1 M 200). Yêu cầu: Xóa đi K chữ số trong N để thu được số N’ sao cho N’ có giá trị nhỏ nhất. (K M). Dữ liệu vào: Cho trong file văn bản XOASO.INP có cấu trúc như sau: Dòng 1: Ghi số hai số nguyên dương N K. Hai 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 XOASO.OUT theo cấu trúc như sau: Dòng 1: Ghi số N’ tìm được. (Vẫn giữ các chữ số 0 ở đầu số nếu có) Ví dụ: XOASO.INP XOASO.OUT XOASO.INP XOASO.OUT 123952 2 1232 95002 2 002 ====== HẾT ====== HỘI THI TIN HỌC TRẺ TỈNH QUẢNG BÌNH LẦN THỨ X ĐÁP ÁN ĐỀ THI CHÍNH THỨC - BẢNG C - THPT Ngày thi 15/07/2009. Thời gian làm bài 150 phút Câu 1: (3,0 điểm) Giải nén xâu Tên file chương trình: GNENXAU.PAS const fi='gnenxau.in1'; fo='gnenxau.ou1; var st,xso:string; f,g:text; i,j,k,n,code:integer; begin assign(f,fi); assign(g,fo); reset(f); rewrite(g); readln(f,st); j:=1; while j<=length(st) do if st[j] in ['0'..'9'] then begin i:=j; xso:=''; while st[i] in ['0'..'9'] do begin xso:=xso+st[i]; i:=i+1; end; val(xso,n,code); for k:=1 to n do write(g,st[i]); j:=i+1 end else begin write(g,st[j]); j:=j+1; end; close(f); close(g); end. Câu 2: (3,5 điểm) Thuê vị trí đặt biển quảng cáo. Tên file chương trình: QC.PAS {$R+} {OK} const fi='qc.in0'; fo='qc.ou0'; type integer=longint; mang=array[1..1000] of integer; var f,g:text; n:integer; d,c,t,tr,dau,QH:mang; procedure nhap; var i,tg:integer; begin assign(f,fi); reset(f); readln(f,n); for i:= 1to n do begin readln(f,d[i],tg,t[i]); qh[i]:=t[i]; c[i]:=d[i]+tg; dau[i]:=i; end; close(f); end; procedure doicho(var a,b:integer); var tg:integer; begin tg:=a; a:=b; b:=tg; end; function max(var a,b:integer):integer; begin max:=a; if a<b then max:=b; end; procedure xuli; var vitri,max1,i,j,x:integer; begin for i:= 1 to n-1 do for j:= i+1 to n do if c[i]>c[j] then begin doicho(c[i],c[j]); doicho(d[i],d[j]); doicho(dau[i],dau[j]); doicho(t[i],t[j]) ; doicho(qh[i],qh[j]); end; {=============QUYHOACH=====================} for i:= 2 to n do {mang t la tien luc dau } for j:=1 to i-1 do if (d[i]>c[j]) and (qh[i]<qh[j]+t[i]) then begin qh[i]:= qh[j] +t[i]; tr[i]:=j; end; {===========TIM LON NHAT===============================} max1:=0; for i:= 1 to n do if QH[i]>max1 then begin max1:=QH[i]; vitri:=i; end; {==========TRUYVET======================================} i:=0; j:=vitri; while j0 do begin i:=i+1; j:=tr[j] ; end; assign(g,fo); rewrite(g); writeln(g,i,' ',max1); max1:=i; j:=0; while vitri0 do begin j:=j+1; d[j]:=dau[vitri]; vitri:=tr[vitri]; end; for i:= max1 downto 1 do write(g,d[i],' '); close(g); end; BEGIN nhap; xuli; END. Câu 3: (3,5 điểm) Xóa số Tên file chương trình: XOASO.PAS {$R+} const fi='xoaso.in7'; fo='xoaso.OU7'; var f,g:text; k,i,j,n,code,a,b:integer; sok,s:string; dd:integer; begin assign(f,fi); assign(g,fo); reset(f); rewrite(g); read(f,s); for i:=length(s) downto 1 do if s[i]=' ' then begin sok:= copy(s,i+1,length(s)-i); break end; val(sok,k,code); writeln(k); delete(s,pos(' ',s), length(s)-pos(' ',s)+1); writeln(s); for i:=1 to k do begin j:=1; dd:=length(s); while j<length(s) do begin val(s[j],a,code); val(s[j+1],b,code); if a>b then begin delete(s,j,1); break end else inc(j); end; if j=dd then delete(s,dd,1); end; write(g,s); close(f); close(g); end. Câu 3: (3,5 điểm) Nối dây điện Tên file chương trình: DAYDIEN.PAS Trong Hội trại hè năm 2009, có N trại của N đơn vị được đánh số từ 1 đến N, trong đó có một trại của Ban tổ chức. Tại mỗi trại có một cây cột điện. Vị trí cây cột điện của trại i được xác định bởi tọa độ (xi, yi). Để cung cấp điện cho N trại, Ban tổ chức phải đặt một máy phát điện ở trại Ban tổ chức và thiết kế một sơ đồ nối dây điện giữa N trại đó sao cho N trại đều cùng có điện. Yêu cầu: Hãy xác định tổng độ dài bé nhất của dây điện mà Ban tổ chức phải sử dụng. Dữ liệu vào: Cho trong file văn bản DAYDIEN.INP có cấu trúc như sau: Dòng 1: Ghi số nguyên dương N là số trại tham gia. (1 ≤ N ≤ 100) Trong N dòng tiếp theo: Mỗi dòng ghi 2 số nguyên dương xi yi là tọa độ của cây cột điện thứ i. (0 < xi yi < 30000) Dữ liệu ra: Ghi ra file văn bản DAYDIEN.OUT theo cấu trúc như sau: Dòng 1: Ghi số dương S là độ dài của dây điện cần sử dụng tìm được. (1 < S < 2100000000) Ví dụ: DAYDIEN.INP DAYDIEN.OUT 4 0 0 0 1 1 0 1 1 3 ====== HẾT ====== Câu 3: (2,5 điểm) Đồ thị HANGCAY.PAS Cổng vào Trung tâm thanh thiếu nhi có một hàng cây gồm N cây cảnh. Hàng cây được đánh số từ 1 đến N tính từ ngoài vào trong. Ban quản lí Trung tâm đã đo được cây thứ i có độ cao là hi. Để cho đẹp, hàng cây phải có độ cao tăng dần tính từ ngoài cổng vào (cây phía ngoài phải thấp hơn cây phía trong). Vì vậy, Ban quản lí Trung tâm quyết định chặt bỏ đi những cây có độ cao không phù hợp và giữ nguyên vị trí các cây còn lại để được một hàng cây có độ cao tăng dần. Yêu cầu: Tìm cách loại bỏ đi một số cây sao cho số cây còn lại là nhiều nhất và hàng cây có độ cao tăng dần. Dữ liệu vào: Cho trong file văn bản HANGCAY.INP, có cấu trúc: Dòng 1: Ghi số nguyên dương N, là số lượng cây ban đầu trong hàng cây (1≤N≤100) Dòng 2: Ghi N số nguyên dương hi (1 ≤ hi ≤ 32767) lần lượt là độ cao của cây thứ i trong hàng cây, tính từ ngoài cổng vào. 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 HANGCAY.OUT, theo cấu trúc: Dòng 1: Ghi số nguyên dương M, là số lượng cây còn lại trong hàng cây sau khi loại bỏ. Dòng 2: Ghi M số nguyên dương là chỉ số của mỗi cây còn lại trong hàng cây sau khi loại bỏ. Các số phải được ghi cách nhau ít nhất một dấu cách. Ví dụ: HANGCAY.INP HANGCAY.OUT 5 5 8 3 4 9 3 1 2 5 (Có nhiều kết quả đúng, chỉ cần đưa ra một kết quả) ===Hết=== Lưu ý: Học sinh tạo một thư mục có tên là số báo danh của mình và chép các file bài làm vào thư mục đó. Câu 2: (4,0 điểm) Cấp số cộng Tên file chương trình: CSC.PAS Người ta định nghĩa: Cấp số cộng là một dãy gồm ít nhất 3 phần tử, trong đó kể từ phần tử thứ hai, mỗi phần tử đều bằng phần tử đứng ngay trước nó cộng với một số không đổi d. Số d được gọi là công sai của cấp số cộng. Cho dãy số gồm N số nguyên a1, a2, ..., an. Ta gọi dãy con của dãy đã cho là dãy thu được bởi việc xoá khỏi dãy đã cho một số phần tử của nó và giữ nguyên thứ tự của các phần tử còn lại. Bản thân dãy đã cho cũng được xem là dãy con của chính nó. Yêu cầu: Hãy tìm một dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho các phần tử trong dãy con lập thành một cấp số cộng với công sai d (1 d 100). Có thể không tồn tại dãy con lập thành cấp số cộng. Giới hạn dữ liệu: 1 N 10000; -30000 ai 30000. Giới hạn thời gian thực hiện chương trình: không quá 3 giây với mọi bộ dữ liệu vào. Dữ liệu vào: Cho trong file văn bản CSC.INP có cấu trúc như sau: Dòng 1: Ghi số nguyên dương N, là số lượng phần tử của dãy. N dòng tiếp theo: Mỗi dòng ghi một số nguyên ai. Dữ liệu ra: Ghi ra file văn bản CSC.OUT theo cấu trúc như sau: Dòng 1: Ghi số -1 nếu không tìm thấy. Ngược lại ghi 2 số nguyên dương k và d, trong đó k là số phần tử của dãy con, d là công sai. Các số được ghi cách nhau ít nhất một dấu cách. K dòng tiếp theo: Mỗi dòng ghi một chỉ số trong dãy đã cho của một phần tử của dãy con tìm được theo thứ tự xuất hiện của chúng trong dãy con. Ví dụ: CSC.INP CSC.OUT 13 6 11 -100 2 -91 4 -90 6 -80 8 -70 9 -69 10 -60 -58 -47 -36 0 1 2