Đề 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

Câu hỏi 1: ABNAME (6 điểm)

An và Bình rất yêu mèo, nhưng bố mẹ hai bạn không cho phép nuôi vì không có không gian. Do đó vào mỗi buổi chiều hai bạn thường cùng nhau đến bãi đất trống gần nhà để cho những con mèo hoang ăn. Hôm nay, đàn mèo hoang này lại sinh thêm những thành viên mới. Và hai bạn quyết định đặt tên cho chúng. Cũng giống như những con mèo khác trong đàn, những con mèo này cũng sẽ được đặt tên theo quy tắc sau:

Chỉ gồm 2 chữ cái ‘A’ và ‘B’
Tên phải không chứa quá countA chữ cái ‘A’
Không chứa quá countB chữ cái ‘B’
Mỗi xâu con gồm các chữ cái ‘A’ liên tiếp có độ dài không quá maxA
Mỗi xâu con gồm các chữ cái ‘B’ liên tiếp có độ dài không quá maxB

9 trang Hữu Vượng 31/03/2023 9220

Download

Bạn đang xem tài liệu "Đề 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

de_thi_de_nghi_mon_tin_hoc_lop_10_ky_thi_olympic_23_3_tinh_d.doc

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

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.
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);
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