›

Đề thi đề nghị môn Tin học Lớp 11 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Chuyên Nguyễn Chí Thanh

 

 

Câu hỏi 1:  (7,0 điểm) Dãy nón

 

Một dãy số nguyên được gọi là dãy nón nếu dãy thỏa mãn điều kiện:

  1. với ;
  2. với .

Yêu cầu: Cho dãy số nguyên . Hãy tìm cách xóa đi ít phần tử nhất để nhận được dãy nón.

Dữ liệu: Vào từ file văn bản LHSEQ.INP: 

Dòng đầu tiên ghi số nguyên dương T (T ≤ 10)là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:

  • Dòng đầu chứa một số nguyên m; (m<=50000)
  • Dòng thứ hai gồm số . 

Kết quả: Ghi ra file văn bản LHSEQ.OUTGồm T dòng, mỗi dòng chứa một số là số phần tử ít nhất được xóa (ghi -1 nếu không có cách xóa thỏa mãn) tương ứng với bộ dữ liệu vào.

Ví dụ:

doc 10 trang Hữu Vượng 31/03/2023 2480
Download
Bạn đang xem tài liệu "Đề thi đề nghị môn Tin học Lớp 11 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Chuyên Nguyễn Chí Thanh", để 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:

  • docde_thi_de_nghi_mon_tin_hoc_lop_11_ky_thi_olympic_23_3_tinh_d.doc

Nội dung text: Đề thi đề nghị môn Tin học Lớp 11 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Chuyên Nguyễn Chí Thanh

  1. Câu hỏi 2: (7,0 điểm) Đoạn con tổng 0 Mã số câu: Cho một dãy số nguyên n phần tử A 1, A2, A3, , An. Một đoạn con liên tiếp của dãy A có điểm đầu L, điểm cuối R (L≤R) là tập hợp tất cả các phần tử A i với (L ≤ i ≤R). Đếm số đoạn con có tổng tất cả các phần tử bằng 0. Dữ liệu vào: Vào từ file văn bảnSUMSEQ0.INP • Dòng đầu là số tự nhiên N 9 • Dòng thứ 2 là N số nguyên A1, A2, A3, , An. ( |Ai| ≤ 10 ) Dữ liệu ra: Ghi ra file văn bảnSUMSEQ0.OUT – ghi số lượng đoạn con tìm được. SUMSEQ0.INP SUMSEQ0.OUT 5 4 2 1 -1 -2 0 Đáp án câu hỏi 2: CÂU ĐÁP ÁN – HƯỚNG DẪN CHẤM ĐIỂM uses math; const f1 = 'lhseq.inp'; f2 = 'lhseq.out'; maxn = trunc(1e5)+3; var a,b,p,q,f,g,vt : array[0 maxn] of longint; n,res,lim,test : longint; procedure swap(var x,y : longint); var tmp : longint; begin tmp := x; x := y; y := tmp; end; procedure sort(l,r : longint); var i,j,x,tmp : longint; begin i := l; j := r; x := a[(l+r) div 2]; repeat while a[i] x do dec(j); if i j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure enter; var i : longint; begin readln(n); for i:=1 to n do begin read(a[i]); 4
  2. 4 Test 04 0.35 5 Test 05 0.35 . . 19 Test 19 0.35 20 Test 20 0.35 6
  3. begin readln(dau,cuoi); inc(head[dau]); inc(head[cuoi]); end; for i:=2 to n+1 do inc(head[i],head[i-1]); for i:=1 to m do with tao[i] do begin u:=dau; v:=cuoi; ds[head[u]]:=v; ds[head[v]]:=u; dec(head[u]); dec(head[v]); end; end; procedure push(V:Longint); begin inc(last); queue[last]:=v; end; function pop:Longint; begin pop:=queue[first]; inc(first); end; procedure bfs; var i,u,v :Longint; begin repeat u:=pop; for i:=head[u]+1 to head[u+1] do begin v:=ds[i]; if not free[v] then begin push(V); free[v]:=true; end; end; until first>last; end; procedure load; var dem,i,j,tg :Longint; begin dem:=0; for i:=1 to n do if not free[i] then begin last:=1; first:=1; queue[1]:=i; free[i]:=true; bfs; inc(dem); a[dem]:=last; end; for i:=1 to dem-1 do for j:=i+1 to dem do if a[i]<a[j] then begin 8