intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Đề thi chọn đội tuyển Quốc gia môn Tin học năm 2022-2023 có đáp án (Vòng 2) - Sở GD&ĐT Quảng Bình

Chia sẻ: _ _ | Ngày: | Loại File: DOC | Số trang:11

26
lượt xem
3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Để đạt được kết quả cao trong kì thi sắp diễn ra, các em học sinh khối lớp 5 có thể tải về tài liệu "Đề thi chọn đội tuyển Quốc gia môn Tin học năm 2022-2023 có đáp án (Vòng 2) - Sở GD&ĐT Quảng Bình" được chia sẻ dưới đây để ôn tập, hệ thống kiến thức môn học, nâng cao tư duy giải đề thi để tự tin hơn khi bước vào kì thi chính thức. Mời các em cùng tham khảo đề thi.

Chủ đề:
Lưu

Nội dung Text: Đề thi chọn đội tuyển Quốc gia môn Tin học năm 2022-2023 có đáp án (Vòng 2) - Sở GD&ĐT Quảng Bình

  1. SỞ GD&ĐT QUẢNG BÌNH KỲ THI CHỌN ĐỘI TUYỂN  DỰ THI CHỌN HỌC SINH GIỎI QUỐC GIA  ĐỀ CHÍNH THỨC NĂM HỌC 2022­2023 Khóa ngày 20 tháng 9 năm 2022 Môn thi: TIN HỌC BÀI THI THỨ HAI Thời gian: 180 phút (không kể thời gian giao đề) SỐ BÁO DANH:…………… Đề gồm có 03 trang và 03 câu  Sử dụng ngôn ngữ lập trình để giải quyết các bài toán sau: (* Phần mở rộng, có thể là PAS hoặc CPP) Câu Tên file bài làm Tên file dữ liệu vào Tên file dữ liệu ra 1 COLOREC.* COLOREC.INP COLOREC.OUT 2 SCHOOL.* SCHOOL.INP SCHOOL.OUT 3 QUEUE.* QUEUE.INP QUEUE.OUT Câu 1. Hình chữ nhật bốn màu (6 điểm). Trên mặt phẳng tọa độ Đề các vuông góc Oxy cho n điểm phân biệt A i(xi, yi) với i =  1, 2, 3, …, N.   Mỗi điểm Ai được tô bởi màu Ci thuộc {1, 2, 3, 4}. Ta gọi hình chữ nhật  bốn màu là hình chữ nhật thỏa mãn hai điều kiện sau: Bốn đỉnh của hình chữ nhật là bốn điểm trong N điểm đã cho và được tô bởi bốn  màu khác nhau. Các cạnh của hình chữ nhật song song với một trong hai trục tọa độ. Yêu cầu: Cho biết tọa độ  và màu của N điểm, hãy đếm số  lượng hình chữ  nhật bốn  màu. Dữ liệu vào: Cho trong file văn bản có tên COLOREC.INP có cấu trúc: Dòng 1: Chứa số nguyên dương N là số lượng điểm trên mặt phẳng (4 ≤ N ≤ 105). Dòng thứ i trong n dòng tiếp theo chứa ba số nguyên xi, yi, ci là thông tin về tọa độ  và màu của điểm thứ i (i = 1, 2, 3, .., N), (|xi|, |yi| ≤ 200). (Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách) Dữ liệu ra: Ghi vào file văn bản có tên COLOREC.OUT với cấu trúc: Dòng 1: Ghi một số nguyên là số lượng hình chữ nhật đếm được. Ví dụ: COLOREC.INP COLOREC.OUT 7 2 0 0 1 0 1 4 2 1 2 2 -1 3 0 -1 1 -1 -1 4     Trang 1
  2. -1 1 1   * Giới hạn: 50% số test ứng với 50% số điểm của bài có 4 ≤ n ≤ 100 Câu 2. Đường đến trường (7 điểm). Ngày 20/9/2022 Sở GD&ĐT Quảng Bình tổ chức kỳ thi chọn đội tuyển chính thức  dự thi học sinh giỏi Quốc gia tại điểm thi trường THPT Chuyên Võ Nguyên Giáp. Tất  cả các bạn đã chuẩn bị khá kỹ càng. Chỉ có điều, các thí sinh dự thi rất lo lắng cho Nam   vì nhà Nam cách điểm thi khá xa và bạn  ấy không xác định được đi đường nào đến   điểm thi là nhanh nhất. Thường ngày mọi người không quan tâm đến điều này, nhưng   hôm nay là kỳ thi rất quan trọng nên không muốn bạn Nam đến trễ.  Bản đồ  thành phố  Đồng Hới gồm có N nút giao thông và M con đường nối các nút  giao thông này. Có 2 loại con đường là đường 1 chiều và đường 2 chiều. Độ dài của mỗi   con đường là một số nguyên dương. Nhà Nam ở nút giao thông 1, điểm thi Trường THPT  Chuyên Võ Nguyên Giáp  ở  nút giao thông N. Vì một lộ  trình đường đi từ  nhà Nam tới   điểm thi có thể gặp nhiều yếu tố khác như là gặp nhiều đèn đỏ, đi qua công trường xây  dựng, ... phải giảm tốc độ cho nên Nam muốn biết là có tất cả bao nhiêu  đường đi ngắn  nhất đi từ  nhà tới điểm thi. Các bạn thí sinh hãy lập trình giúp Nam giải quyết bài toán  này. Dữ liệu vào: Cho trong file văn bản có tên SCHOOL.INP có cấu trúc: Dòng 1: Chứa hai số nguyên N và M (1 ≤ N ≤ 5000; 1 ≤ M ≤ 20000). M dòng tiếp theo, mỗi dòng ghi 4 số nguyên dương K, U, V, L. Trong đó: + K = 1 có nghĩa là có đường đi một chiều từ U đến V với độ dài L. + K = 2 có nghĩa là có đường đi hai chiều giữa U và V với độ dài L. (1 ≤ U,V ≤  N; L ≤ 32000) (Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách) Dữ liệu ra: Ghi vào file văn bản có tên SCHOOL.OUT với cấu trúc: Dòng 1: Ghi 1 số là độ dài đường đi ngắn nhất. Dòng 2: Ghi 1 số là số lượng đường đi ngắn nhất.  Biết rằng số lượng đường đi ngắn nhất không vượt quá phạm vi int64 trong pascal  hay long long trong C++. Ví dụ:     Trang 2
  3. SCHOOL.INP SCHOOL.OUT 3   2  4 1   1   2   3 1 2   2   3   1 Câu 3. Xếp hàng (7 điểm). Để  trình diễn một tiết mục trong màn khai mạc Đại hội thể  thao quốc tế, đạo  diễn Hùng đã mời n vận động viên có chiều cao khác nhau từng đôi  một tham gia. Theo  kịch bản, n vận động viên sẽ  được xếp thành một hàng dọc, đầu hàng ở  phía khán đài  A (khán đài chứa các khách mời quốc tế), cuối hàng  ở  phía khán đài B (khán đài có  nhiều du khách và các quan chức địa phương). Đạo diễn muốn rằng từ phía khán đài A,   khán giả có thể nhìn thấy P vận động viên, còn từ phía khán đài B khán giả có thể nhìn   thấy Q vận động viên. Một vận động viên được nhìn thấy từ phía khán đài A nếu như  tất cả  các vận động viên đứng trước (theo chiều từ  đầu hàng đến cuối hàng) đều có  chiều cao thấp hơn vận động viên này. Một vận động viên được nhìn thấy từ phía khán   đài B nếu như  tất cả  các vận động viên đứng sau (theo chiều từ  đầu hàng đến cuối   hàng) đều có chiều cao thấp hơn vận động viên này. Ví dụ: Có 9 vận động viên được xếp theo thứ tự với dãy chiều cao tương ứng là  3, 2, 4, 1, 9, 8, 7, 5, 6 thì từ khán đài A (ở phía bên trái) có thể nhìn thấy 3 người (với chiều cao là 3, 4, 9), còn từ  khán đài B (ở phía bên phải) có thể nhìn thấy 4 người (với chiều cao là 6, 7, 8, 9).  Yêu cầu: Hãy giúp đạo diễn xác định xem có bao nhiêu cách xếp n vận động viên   thành hàng dọc thoả mãn điều kiện đặt ra.  Dữ liệu vào: Cho trong file văn bản có tên QUEUE.INP có cấu trúc: Dòng đầu tiên ghi ba số nguyên dương n, P, Q (n   2000; P, Q   n). Dòng thứ hai gồm n số nguyên dương là các độ cao của n vận động viên được mời   tham gia thực hiện tiết mục trình diễn.  (Hai số  liên tiếp trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu   cách) Dữ liệu ra: Ghi vào file văn bản có tên QUEUE.OUT với cấu trúc:  Dòng 1:  Gồm một số  nguyên là phần dư  trong phép chia số  lượng cách xếp tìm   được cho 109+7. Ví dụ: QUEUE.INP QUEUE.OUT 3   2   1  1 1   2   3 Giải thích: Trong số 6 cách xếp 3 vận động viên thành một hàng dọc, có một  cách  duy nhất các vận động viên được xếp theo thứ tự chiều cao là 2, 1, 3 thoả mãn yêu cầu      Trang 3
  4. đặt ra: Nhìn từ khán đài A thấy được 2 vận động viên 2,3; nhìn từ khán đài B thấy được   1 vận động viên 3 * Giới hạn ? ≤ 10: 30% số điểm ? ≤ 500; ? = 1: 30% số điểm ? ≤ 500: 20% số điểm ? ≤ 2000: 20% số điểm  YÊU CẦU CHUNG I. PHƯƠNG PHÁP ­ Bài thi của thí sinh được chấm bằng chương trình chấm tự động Themis. ­ Test của các bài được đặt cấu hình như sau: + Câu 1: GK tạo ít nhất 12 test,  mỗi test tương ứng với số điểm 6đ/số test. Thời gian  cho mỗi test của câu 1 là 1 giây. + Câu 2: GK tạo ít nhất 14 test,  mỗi test tương  ứng với số  điểm 7đ/số  test, thời gian  cho mỗi test của câu 2 là 1 giây. + Câu 3: GK tạo ít nhất 14 test,  mỗi test tương  ứng với số  điểm 7đ/số  test, thời gian  cho mỗi test của câu 2 là 1 giây. ­ Tổng điểm được làm tròn đến một chữ số ở hàng thập phân. II. CHƯƠNG TRÌNH GỢI Ý Câu 1. Hình chữ nhật bốn màu (6 điểm).     COLOREC.* Program COLOREC; Uses Math; Const   minXY =­200;   maxXY =200;   fi='COLOREC.INP';   fo='COLOREC.OUT'; Var   res :LongInt;   A :Array[minXY..maxXY,minXY..maxXY] of Byte;   C :Array[1..4,1..4] of integer;   f:Text;   maxx,may,mix,miy:integer;   procedure Enter;   var     i,n :LongInt;     Trang 4
  5.     x,y :SmallInt;   begin     assign(f,fi);     reset(f);     Read(f,n);     maxx:=­201;     mix:=201;     may:=­201;     miy:=201;     FillChar(A,SizeOf(A),0);     for i:=1 to n do     begin     Read(f,x,y,A[x,y]);     if x>maxx then maxx:=x     else if xmay then may:=y     else if y0) then               Inc(C[Min(A[x1,y],A[x2,y]),Max(A[x1,y],A[x2,y])]);           Inc(res,C[1,2]*C[3,4]+C[1,3]*C[2,4]+C[1,4]*C[2,3]);         end;   end; Begin   Enter;   Solve;   Assign(f,fo); Rewrite(f);   Write(f,res);   Close(f); End.     Trang 5
  6. Câu 2. Đường đến trường (7 điểm).     SHOOL.* const    tfi='school.inp';    tfo='school.out';    maxn=5001; type    PtrNode=^Node;    Node = record id: integer; Ts: integer; next: PtrNode; end;    arr1=array[1..maxn] of PtrNode;    arr2=array[1..maxn] of integer;    arr3=array[1..maxn] of longint;    arr4=array[1..maxn] of byte;    arr5=array[1..maxn] of int64; var    fi, fo: text;    N,M: integer;    a: arr1;    q: arr2;    qn: integer;    kc: arr3;    color: arr4;    sl: arr5;    cs: arr2; procedure initq; begin    qn:=0; end; procedure put(u: integer); begin    inc(qn);    q[qn]:=u; end; function get: integer; var u,i: integer; begin    u:=1;    for i:=2 to qn do       if kc[q[i]]
  7. begin    qempty:=(qn=0); end; procedure ThemCanh(u,v,L: integer); var t: PtrNode; begin    new(t);    t^.id:=v; t^.Ts:=L;    t^.next:=a[u];    a[u]:=t; end; procedure dijstra; var u,v: integer;     t: PtrNode; begin    initq;    fillchar(color,sizeof(color),0);    put(1); color[1]:=1; kc[1]:=0;    repeat       u:=get; color[u]:=2;       t:=a[u];       while tnil do          begin             v:=t^.id;             if (color[v]=1) and (kc[v]>kc[u]+t^.Ts) then                kc[v]:=kc[u]+t^.Ts;             if color[v]=0 then                begin                   put(v);                   kc[v]:=kc[u]+t^.Ts;                   color[v]:=1;                end;             t:=t^.next;          end;    until qempty; end; procedure sort(k,l: integer); var r: longint;     i,j, tg: integer; begin    r:=kc[cs[(k+l) div 2]];    i:=k; j:=l;    repeat     Trang 7
  8.       while kc[cs[i]]r do dec(j);       if ij;    if k
  9.       begin          read(fi,k,u,v,L);          ThemCanh(u,v,L);          if k=2 then ThemCanh(v,u,L);       end; end; procedure main; begin    assign(fi,tfi); reset(fi);    assign(fo,tfo); rewrite(fo);    doc;    tim;    writeln(fo,kc[n]);    writeln(fo,sl[n]);    close(fi); close(fo); end; BEGIN    main; END. Câu 3. Xếp hàng (7 điểm).     QUEUE.* #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; #define LL long long  #define uLL unsigned long long  #define FOR(i,l,r) for(int i = l; i  l; ­­i) #define pi pair #define pii pair #define mp make_pair #define fi first     Trang 9
  10. #define se second const int maxN = 2001; const LL MOD = 1e9 + 7; int tcases = 1; ///////////////////////////////////////////////////////////////////////////////////////////////////////////// int N,P,Q; LL F[maxN][maxN],C[maxN][maxN],H[maxN]; LL cal(int len,int p){     if(F[len][p] >= 0) return F[len][p];     return 0; } void testcase(){     cin >> N >> P >> Q;     //     F[1][1] = 1;     FOR(i,0,N) FOR(j,0,N){         if(j > i){             F[i][j] = 0;         }else if(i == j){             F[i][j] = 1;         }else if(j == 0){             F[i][j] = 0;         }else if(j == 1){             F[i][j] = H[i ­ 1];         }else F[i][j] = (F[i ­ 1][j ­ 1] + 1LL * (i ­ 1) * F[i ­ 1][j]) % MOD;     }     LL res = 0;     FOR(i,1,N){         res += ((cal(i ­ 1,P ­ 1) * cal(N ­ i,Q ­ 1)) % MOD * C[i ­ 1][N ­ 1]) % MOD;         res %= MOD;     }     cout 
  11.     cin.tie();     cout.tie();     //     freopen("QUEUE.INP","r",stdin);     freopen("QUEUE.OUT","w",stdout);     //cin >> tcases;     init();     FOR(i,1,tcases) testcase();     return 0; }     Trang11
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2