Tài liệu Chuyên đề duyệt có tính toán t10.2017 chuan

CHUYÊN ĐỀ DUYỆT CÓ TÍNH TOÁN A. MỤC ĐÍCH Chuyên đề này cung cấp cho học sinh những kiến thức và kĩ năng trọng tâm về ứng dụng duyệt có tính toán. Cụ thể: a) Về kiến thức: Cung cấp, hệ thống cho học sinh các kiến thức cơ bản, trọng tâm về những ứng dụng của phương pháp duyệt có tính toán trong lập trình, đáp ứng yêu cầu của kì thi chọn học sinh giỏi các cấp. b) Về kĩ năng: - Nhận biết được bài toán cụ thể có thể giải bằng duyệt có tính toán. - Rèn luyện cho học sinh kĩ năng duyệt có tính toán áp dụng để giải một số bài toán ứng dụng phương pháp duyệt. B. NỘI DUNG I. Tư tưởng Duyệt toàn bộ. Sau đó có thể tính toán trước một phần để giảm độ phức tạp của thuật toán. II. Bài toán cơ bản A 1. Bài toán 1. Cho dãy số nguyên A1,A2,…,AN ( i <=109; N<=106) và một số nguyên dương k (k<=106) là số cặp chỉ số(i, j) (1 ≤ i < j < N; k ≤ 10 6). Yêu cầu: với mỗi cặp j chỉ số (i,j) hãy tính  h i Ah (Tính tổng của k đoạn với mỗi cặp chỉ số (i,j) khác nhau). Input: Vào từ file văn bản BT1.INP có cấu trúc như sau: - Dòng đầu gồm hai số nguyên N, S. Dòng thứ 2 gồm N số nguyên A1,A2,…,AN . k dòng tiếp theo chứa k cặp (i, j) theo yêu cầu. Output: Ghi ra file văn bản BT1.OUT gồm k dòng ghi tổng k đoạn . Ví dụ: BT1.INP BT1.OUT 10 3 16 12 4 5 8 8 5 32 23 12 14 25 69 37 29 68 Ràng buộc: - Có 60% test ứng với 40% điểm của bài có n, k ≤ 5000. Có 40% test ứng với 30% điểm của bài có n, k ≤ 106. Hướng dẫn 1 + Mức độ 1. Duyệt toàn bộ k cặp (i, j). for i:=1 to k do begin read(f1,x,y); sum:=0; for h:=i to j do sum:=sum+a[j]; end; Độ phức tạp O(k,n); + Mức độ 2. Ta có thể giảm độ phức tạp của thuật toán bằng cách tính trước mảng sum. Gọi sum[i] là tổng các phần tử từ A1,A2,…,AN. Mảng sum được tính như sau: s[0]:=0; for i:=1 to n do s[i]:=s[i-1]+a[i]; Sau đó, tổng đoạn được tính như sau: for l:=1 to k do sum: =sum[j] - s[i-1]); Độ phức tạp (O(max(n,k)). Chương trình mẫu CONST fi='BT2.inp'; fo='BT2.out'; maxN=trunc(1e6)+1; TYPE data=longint; VAR a:array[1..maxN] of data; s:array[0..maxN] of int64; f1,f2:text; n,k:data; procedure var enter; i:data; begin read(f1,n,k); for i:=1 to n do read(f1,a[i]); end; procedure var sub1; i,j,x,y:data; sum:int64; begin 2 for i:=1 to k do begin read(f1,x,y); sum:=0; for j:=x to y do sum:=sum+a[j]; writeln(f2,sum); end; end; procedure var chuanbi; i:data; begin s[0]:=0; for i:=1 to n do s[i]:=s[i-1]+a[i]; end; procedure var sub2; x,y,i,j:data; begin chuanbi; for i:=1 to k do begin read(f1,x,y); writeln(f2,s[y]-s[x-1]); end; end; procedure main; begin assign(f1,fi); reset(f1); assign(F2,fo); rewrite(f2); enter; if n<=5000 then sub1 else sub2; close(f1); close(F2); end; 3 BEGIN main; END. A 2. Bài toán 2. Cho dãy số nguyên A1,A2,…,AN ( i <=109; N<=105) và một số nguyên dương S (S<=109). Yêu cầu: Đếm số lượng dãy con liên tiếp của dãy A1,A2,…,AN có số phần tử lớn hơn 3 và có tổng bằng S. Input: Vào từ file văn bản BT2.INP có cấu trúc như sau: - Dòng đầu gồm hai số nguyên N, S. Dòng thứ 2 gồm N số nguyên A1,A2,…,AN . Output: Ghi ra file văn bản BT2.OUT một số nguyên duy nhất là số lượng dãy con liên tiếp có số phần tử lớn hơn 3 và có tổng bằng S. Ví dụ: BT2.INP BT2.OUT 10 45 16 12 4 5 8 8 5 32 23 12 2 Ràng buộc: - Có 40% test ứng với 40% điểm của bài có n ≤ 400. Có 30% test ứng với 30% điểm của bài có n ≤ 5000. Có 30% test ứng với 30% điểm của bài có n ≤ 105. Hướng dẫn *. Thuật toán 1: - Lần lượt liệt kê tất cả các khả năng của nghiệm (Gọi là phần thử - duyệt). - Với mỗi vector nghiệm ta kiểm tra xem nghiệm đó của thỏa mãn điều kiện của đầu bài hay không. Function kiemtra(i,j:longint):Boolean; Var sum:int64; k:longint; Begin Sum:=0; For k:= i to j do sum:=sum+a[k]; Exit(sum=S); End; **************** Procedure try; Var i,j:longint; Begin Count:=0; For i:= 1 to n -3 do For j:= i+3 to n do If kiemtra(i,j) then inc(count); End; 4 Nhận xét: Với thuật toán trên thì độ phức tạp là O(n3) nên chỉ chạy được với n<=400. *. Thuật toán 2: Cài tiến việc kiểm tra từ O(n) về O(1). - Ta tính toán tổng tất cả các phần tử a[i] đến a[j]. Như vậy khi kiểm tra chỉ việc lấy ra chứ không phải tính toán nữa. - Gọi mảng L là mảng một chiều mà L[i] là tổng các phần tử từ phần tử 1 đến phần tử thứ i. Procedure chuanbi; Var i:longint; Begin Fillchar(L,sizeof(L),0); For i:= 1 to n do L[i]:=L[i-1]+a[i]; End: **************** Function kiemtra(i,j:longint):Boolean; Begin Exit(L[j]-L[i-1]=S); End; **************** Procedure try; Var i,j:longint; Begin Count:=0; For i:= 1 to n -3 do For j:= i+3 to n do do If kiemtra(i,j) then inc(count); End; Nhận xét: - Với thuật toán trên do ta tính trước được tổng các phần tử từ a[i] đến a[j] nên với mỗi lần duyệt ở thủ tục Try thì ta chỉ cần lấy kết quả ra để kiểm tra => Độ phức tạp của thuật toán là O(n2). Với độ phức tạp này ta có thể chạy được với n<=5000. (Ta cũng có thể làm bằng cách tính tổng cộng dồn sau mỗi khi tăng j) *. Thuật toán 3: Ta tối ưu thuật toán ở phần thử (Phần duyệt). - Với mỗi phần tử thứ i: Ta tìm kiếm xem có bao nhiêu chỉ số j mà (j>i+3, L[i1] + S =L[j]) - Việc tìm j thỏa mãn điều kiện trên ta có thể tìm bằng thuật toán tìm kiếm nhị phân với độ phức tạp là O(log n). - Để tìm kiếm được ta phải sắp xếp tăng dần mảng Q (Chính là mảng L nhưng có thêm phần chỉ số). 5 Cụ thể ta làm như sau: - Tính mảng L - Độ phức tạp O(n). - Tính mảng Q. For i:= 1 to n do Begin Q[i].GT:=L[i]; Q[i].CS:=i; End; - Sắp xếp (Quicksort) mảng Q theo trường GT - Độ Phức tạp O(nlogn) - Duyệt: Với mỗi i ta tìm Q[j] mà Q[j].GT = S + L[i-1] và Q[i].CS>i+3. Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phẩn kiemtra có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Có thể chạy được với n<=105). Muốn viết được thuật toán trên ta phải viết được thuật toán tìm kiếm nhị phân và thuật sắp xếp quicksort: *. Thuật toán tìm kiếm nhị phân: Function Nhiphan(L,H:Longint):Longint; Var Dau,Cuoi,Giua;Longint; Begin Dau:=L; Cuoi:=H; Giua:=(Dau+Cuoi) Div 2; While (a[Giua]<>K ) and (Dau<=Cuoi) do Begin If A[giua]>K then Cuoi:=giua-1 Else Dau:=Giua+1; Giua:=(Dau+Cuoi) Div 2; End; If a[giua]=K then Exit(Giua) else Exit (0); End; *. Thuật toán sắp xếp nhanh (Quicksort). Procedure Quicksort(L,H:Longint); Var i,j:Longint; x,tg:Longint; Begin i:=L; j:=H; x:=a[(L+H) Div 2]; Repeat 6 While a[i].keyx.key do dec(j); If i<=j then Begin Đỗi chỗ a[i] và a[j] Inc(i); Dec(j); End; Until i>j; If Ly.gt then Exit (1) Else Exit(-1); End; Procedure Quicksort(L,H:Longint); Var i,j:Longint; x,tg:Longint; Begin i:=L; j:=H; x:=a[(L+H) Div 2]; Repeat 7 While a[i].keyx.key do dec(j); If i<=j then Begin Đỗi chỗ a[i] và a[j] Inc(i); Dec(j); End; Until i>j; If Li+3. Như vậy: Với thuật toán này thì phần duyệt có độ phức tạp là O(n) còn phần kiemtra có chi phí là O(logn) => Toàn thuật toán có chi phí là O(nlogn) => Có thể chạy được với n<=105). Chương trình tham khảo CONST fi='BT2.inp'; fo='BT2.out'; maxN=trunc(1e5)+1; TYPE data=longint; logs=record gt:int64; cs:data; end; VAR f1,f2:text; a:array[1..maxN] of data; n,s,kq:data; l:array[0..maxN] of int64; q:array[1..maxN] of logs; procedure enter; var i:data; begin read(f1,n,s); l[0]:=0; for i:=1 to n do begin read(f1,a[i]); l[i]:=l[i-1]+a[i]; 8 end; end; function kiemtra(i,j:data):boolean; var sum:int64; k:data; begin sum:=0; for k:=i to j do sum:=sum+a[k]; exit(sum=s); end; procedure sub1; var i,j:data; begin for i:=1 to n-3 do for j:=i+3 to n do if kiemtra(i,j) then inc(kq); write(f2,kq); end; procedure sub2; var i,j:data; begin for i:=1 to n-3 do for j:=i+3 to n do if l[j]-l[i-1]=s then inc(kq); write(F2,kq); end; procedure chuanbi; var i:data; begin for i:=1 to n do begin q[i].gt:=l[i]; q[i].cs:=i; end; end; function check(a,b:logs):boolean; begin if a.gtj; if i=i+3 then begin res:=mid; c:=mid-1; end else d:=mid+1; end else if q[mid].gt>s+l[i-1] then c:=mid-1 else d:=mid+1; end; exit(res); end; function find2(i:data):data; var d,c,mid,res:data; 10 begin d:=1; c:=n; res:=0; while (d<=c) do begin mid:=(d+c) div 2; if q[mid].gt=s+l[i-1] then begin if q[mid].cs>=i+3 then begin res:=mid; d:=mid+1; end else d:=mid+1; end else if q[mid].gt>s+l[i-1] then c:=mid-1 else d:=mid+1; end; exit(res); end; procedure sub3; var tmp1,tmp2,i:data; begin chuanbi; sort(1,n); for i:=1 to n do begin tmp1:=find1(i); tmp2:=find2(i); if (tmp1<>0) and (tmp2<>0) then kq:=kq+tmp2-tmp1+1; end; write(f2,kq); end; procedure main; begin assign(F1,fi); reset(F1); assign(F2,fo); rewrite(F2); enter; kq:=0; if n<=400 then sub1 else if n<=5000 then sub2 else sub3; close(F1); close(F2); end; 11 BEGIN main; END. 3. Bài tập 3: ESEQ Cho dãy số nguyên A gồm N phần tử A1, A2, .., AN, tìm số cặp chỉ số i, j thỏa mãn: i  p 1 Ap  N  q j Aq với 1 ≤ i < j ≤ N Input: Vào từ file vãn bản ESEQ.INP có dạng: - Dòng ðầu là số nguyên dýõng N (2 ≤ N ≤ 105) Dòng tiếp theo chứa N số nguyên A1, A2, .., AN (|Ai|<109), các số cách nhau một dấu cách. Output: Ghi ra file vãn bản ESEQ.OUT gồm một số là số cặp tìm ðýợc. Ví dụ: ESEQ.INP 3 101 ESEQ.OUT 3 Hýớng dẫn - Duyệt i,j: Với i là phần tử cuối cùng của ðoạn 1 và j là phần tử ðầu tiên của ðoạn 2. - Với mỗi i,j ta tìm tổng của ðoạn 1 va tổng của ðoạn 2. mất O(n). => Ðộ phức tạp của cả thuật toán là O(n3). Mã code nhý sau: For i:=1 to n-1 do For j:=i+1 to n do Begin S1:=0; For k:=1 to i do S1:=S1+a[k]; S2:=0; For k:=j to n do S2:=S2+a[k]; If S1=S2 then inc(kq); End; Cải tiến 1: ta cải tiến phần kiểm tra từ O(n) về O(1) Bằng cách tính trýớc mảng cộng dồn. - Gọi mảng L. Trong ðó L[i] là tổng các phần tử từ phần tử 1 ðến phần từ i. - Gọi mảng R. Trong ðó L[j] là tổng các phần tử từ phần tử j ðến phần từ n. Thuật toán trên trở thành. For i:=1 to n-1 do For j:=i+1 to n do Begin If L[i]=R[j] then inc(kq); End; 12 Cải tiến 2: Cải tiến phần duyệt. Với mỗi i Ta tìm kiếm nhị phân trên mảng R=L[i]. Ðể ðếm ðýợc có bao nhiêu R[j]=L[i] ta phải sắp xếp mảng R theo giá trị ðồng thời cũng phải lýu chỉ số ban ðầu ðể kiểm tra thỏa mãn ðiều kiện (ix do Dec(j); 13 if i<=j then Begin tg:=sp[i]; sp[i]:=sp[j]; sp[j]:=tg; inc(i); dec(j); end; until i>j; if il then quicksort(l,j); end; Function Lan(k,l:longint):longint; Var tg,l1:longint; Begin tg:=0; l1:=l; While (l1>0) and (sp[l1].gt=st[k]) do Begin if sp[l1].cs>k then tg:=tg+1; Dec(l1); end; l1:=l+1; While (l1<=n) and (sp[l1].gt=st[k]) do Begin if sp[l1].cs>k then tg:=tg+1; inc(l1); end; Exit(tg); end; Function tknp(k:longint):longint; Var dau,cuoi,giua:longint; Begin dau:=1; cuoi:=n; while (dau<=cuoi) do Begin giua:=(dau+cuoi) Div 2; if sp[giua].gt=st[k] then exit(giua); if sp[giua].gt0 then Kq:=kq+Lan(i,tg); end; end; Procedure ghikq; Var f:text; Begin Assign(f,fo); rewrite(f); Write(f,kq); Close(f); end; BEGIN Docdl; quicksort(1,n); Xuli; Ghikq; END. Lýu ý: - Phải có hàm Lan sang hai bên vì ðiều kiện ðầu bài ix do dec(j); if i<=j then Begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); Dec(j); end; until i>j; 16 if il then quicksort(l,j); end; Function lan(l,k:longint):longint; Var kq1:longint; l1:longint; Begin if k=0 then exit(0); kq1:=0; l1:=k; While (l1>l) and (a[l1]=a[k]) do Begin inc(kq1); dec(l1); end; l1:=K+1; While (l1<=n) and (a[l1]=a[k]) do Begin inc(kq1); inc(l1); end; Exit(kq1); end; Function tknp(l,h,x:longint):longint; Var dau,cuoi,giua:longint; Begin Dau:=l; cuoi:=h; While dau<=cuoi do Begin giua:=(dau+cuoi) div 2; if a[giua]=x then exit(giua); if a[giua]0 then kq:=kq+lan(i,kq1); end; end; procedure ghikq; Var f:text; Begin Assign(f,fo); rewrite(f); Write(f,kq); Close(f); end; BEGIN Docdl; Quicksort(1,n); Xuli; Ghikq; END. 5.Bài tập 5. Cam sành Hàm Yên (đề thi trại hè Hùng Vương năm 2017 môn Tin lớp 10). Nhân dịp Trại hè Hùng Výõng nãm nay tổ chức tại tỉnh Tuyên Quang, ðýợc biết ở huyện Hàm Yên có loại cam sành rất nổi tiếng nên các ðoàn cùng nhau ðến thãm nông trang trồng cam sành của gia ðình ông Nghiệp. Nông trang trồng cam nhà ông ðýợc trồng trên núi cao, khí hậu mát mẻ và ðýợc týới bằng nýớc nguồn từ ðỉnh núi nên cam có vị ngọt mát và giá trị dinh dýỡng cao. Trong các ðoàn ðến tham quan có N ngýời muốn mua cam. Do mọi ngýời muốn nhýờng nhau nên mỗi ngýời chỉ mua một quả, ngýời thứ i cho biết sẵn sàng trả pi(ðồng) cho một quả cam. Ông Nghiệp quyết ðịnh lựa chọn ðýa ra một mức giá cố ðịnh là (ðồng) cho mỗi quả cam trong výờn. Vì rất thích tính cách hào phóng của khách nên ông sẽ bán với giá cho tất cả những ngýời sẵn sàng trả giá lớn hõn . Ngoài ra, nếu có những ngýời trả giá ðúng bằng , ông chỉ bán duy nhất cho một ngýời khách ðến sớm nhất. Tuy hiếu khách nhýng vì miếng cõm manh áo nên ông Nghiệp vẫn muốn thu ðýợc số tiền nhiều nhất có thế. Hãy giúp ông Nghiệp lựa chọn mức giá là một số 18 nguyên ðể có thể thu ðýợc nhiều tiền nhất từ việc bán cam cho vị khách nói trên. Biết số cam trong výờn ðảm bảo ðủ cho tất cả khách tới thãm. Input: Vào từ file vãn bản ORANGE.INP có cấu trúc nhý sau: - Dòng ðầu chứa số nguyên dýõng N là số lýợng khách muốn mua cam; Dòng sau ghi N số nguyên dýõng p1, p2, … ,pN ( pi≤ 106) mỗi số cách nhau bởi một dấu cách. Output: Ghi ra file vãn bản ORANGE.OUT một số nguyên duy nhất là số tiền nhiều nhất mà ông Nghiệp có thể thu ðýợc. Ví dụ: ORANGE.INP 4 1254 ORANGE.OUT 8 Ràng buộc: - Có 30% số test ứng với 30% số ðiểm của bài có N, pi ≤ 1000, pi ≠ pj ,∀i ≠ j; - Có 30% số test khác ứng với 30% số ðiểm của bài có N≤ 1000, pi ≠ pj ,∀i ≠ j; - Có 20% số test khác ứng với 20% số ðiểm của bài có N ≤ 105, pi ≠ pj , ∀i ≠ j; - Có 20% số test còn lại ứng với 20% số ðiểm của bài có N ≤ 105. Hýớng dẫn - Có 30% số test ứng với 30% số ðiểm của bài có N, pi ≤ 1000, pi ≠ pj ,∀i ≠ j; Duyệt từng giá trị k = 1 → 1000, kiểm tra trực tiếp từng khách. - Có 30% số test khác ứng với 30% số ðiểm của bài có N≤ 1000, pi ≠ pj ,∀i ≠ j; Duyệt từng giá trị k= p1, … ,pN . - Có 20% số test khác ứng với 20% số ðiểm của bài có N ≤ 105, pi ≠ pj , ∀i ≠ j; Sắp xếp, thử từng giá trị = p1, … , pN . Với k=pi , số ngýời mua ðýợc là n−i + 1 - Có 20% số test còn lại ứng với 20% số ðiểm của bài có N ≤ 105. Sắp xếp tãng dần. Giả sử từ ngýời thứ tới ngýời thứ ðýợc phép mua. Nếu trong những ngýời này có nhiều ngýời cùng giá (hay p i=pi+1 ), giá mua sẽ là pi − 1. Nếu có duy nhất 1 ngýời có giá pi, giá mua sẽ là pi . Chýõng trình tham khảo USES math; CONST fi='ORANGE.inp'; fo='ORANGE.out'; oo=trunc(1e5)+1; maxN=trunc(1e6); TYPE data=longint; VAR a:array[0..maxN] of data; f1,f2:text; n,tmp:data; 19 procedure enter; var i:Data; begin readln(F1,n); tmp:=0; for i:=1 to n do begin read(f1,a[i]); tmp:=max(tmp,a[i]); end; end; procedure sort(l,h:data); var tmp,mid,i,j:data; begin i:=l; j:=h; mid:=a[(l+h) div 2]; repeat while a[i]mid do dec(J); if i<=j then begin tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp; inc(I); dec(J); end; until i>j; if ii then c:=mid-1 else d:=mid+1; end; exit(res); end; 20