Đề thi đề nghị môn Tin học Lớp 10 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Phạm Văn Đồng

Nội dung text: Đề thi đề nghị môn Tin học Lớp 10 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Phạm Văn Đồng

1. Hướng dẫn giải câu hỏi 2: Code tham khảo bài 02 program bai1; const fi = 'xoaso.inp'; fo = 'xoaso.out'; nm = 100000; var s: ansistring; n, k, top: longword; stack: array[1 nm] of char; procedure inp; begin readln(s); readln(k); n := length(s); end; procedure sol; var i: longword; begin n := length(s); top := 1; stack[top] := s[1]; for i := 2 to n do begin while (k > 0) and (top > 0) and (stack[top] < s[i]) do begin dec(k); dec(top); end; inc(top); stack[top] := s[i]; end; for i := 1 to (top-k) do write(stack[i]); end; begin assign(input, fi); reset(input); assign(output, fo); rewrite(output); inp; sol; close(input); close(output); end. * Bộ test: (gồm 10 test kèm theo đĩa CD) * Thang điểm: Mỗi test đúng được 0.7 điểm - Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh giá bài làm và cho tối đa 2 điểm.
2. Hướng dẫn giải câu số 03: Thuật toán đề nghị: Tìm kiếm nhị phân Rất khó để xác định khoảng cách nhỏ nhất giữa hai con bò bất kì là lớn nhất. Ta nhận thấy rằng kết quả của bài toán sẽ nằm đâu đó trong đoạn từ 1 đến (x max - xmin). Chính vì vậy ta sẽ tìm kiếm nhị phân theo khoảng cách trong đoạn [1 xmax - xmin]. Với mỗi giá trị khoảng cách K, ta kiểm tra nếu buộc các con bò với khoảng cách nhỏ nhất lớn hơn hoặc bằng K có thỏa mãn không (buộc đủ C con bò), nếu thỏa thì ghi nhận kết quả hiện tại và thu hẹp không gian tìm kiếm trong đoạn [K+1 x max - xmin], nếu không thỏa thì tìm trong đoạn [1 K-1]. * Chương trình: program CHANBO; const fi='chanbo.inp'; fo='chanbo.out'; maxn=100005; var f:text; a:array [1 maxn] of int64; n,c:longint; res:int64; ok:boolean; procedure nhap; var i:longint; begin assign(f,fi); reset(f); readln(f,n,c); for i:=1 to n do readln(f,a[i]); close(f); end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i);
3. var l,r,mid:int64; begin l:=a[1]; r:=a[n]; while l<=r do begin mid:=(l+r) div 2 ; tinh(mid); if ok then begin l:=mid+1; res:=mid; end else r:=mid-1; end; end; procedure xuat; begin assign(f,fo); rewrite(f); write(f,res); close(f); end; begin nhap; sort(1,n); chat; xuat; end. * Bộ test: (gồm 10 test kèm theo đĩa CD) * Thang điểm: Mỗi test đúng được 0.7 điểm - Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh giá bài làm và cho tối đa 2 điểm. HẾT