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

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

Thêm vào BST

Báo xấu

52
lượt xem 3
download

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

Luyện tập với “Đề thi chọn đội tuyển Quốc gia môn Tin học năm 2022-2023 có đáp án (Vòng 1) - Sở GD&ĐT Quảng Bình” được chia sẻ dưới đây sẽ giúp bạn ôn tập và nâng cao kỹ năng giải bài tập đề thi nhằm chuẩn bị cho bài thi sắp diễn ra đạt kết quả cao. Mời các bạn cùng tham khảo chi tiết đề thi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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 1) - Sở GD&ĐT Quảng Bình

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 20222023 Khóa ngày 20 tháng 9 năm 2022 Môn thi: TIN HỌC BÀI THI THỨ NHẤT Thời gian: 180 phút (không kể thời gian giao đề) SỐ BÁO DANH:…………… Đề gồm có 03 trang và 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 SALE.* SALE.INP SALE.OUT 2 SEASNAIL.* SEASNAIL.INP SEASNAIL.OUT 3 IMPONET.* IMPONET.INP IMPONET.OUT Câu 1. Mua hàng (6 điểm). Một cửa hàng có N món hàng được bày bán trên quầy theo thứ tự từ trái sang phải, với số hiệu lần lượt từ 1..N. Món hàng thứ i có giá tiền là Ai. Nhân dịp trung thu, chủ cửa hàng quyết định thực hiện chính sách giảm giá. Cụ thể với món hàng thứ i, gọi B là mảng giá tiền của các món hàng còn trên quầy nằm bên trái i có giá tiền rẻ hơn Ai , sau khi sắp xếp B tăng dần, nếu số lượng phần tử của B không nhỏ hơn K thì có thể mua món hàng i với giá BK. Ngược lại, nếu số lượng phần tử của B nhỏ hơn K thì món hàng i sẽ vẫn giữ giá cũ. Một món hàng khi được bán thì sẽ được đem đi khỏi quầy. An là một người đam mê mua sắm. An đứng đây từ chiều và muốn mua hết tất cả các món hàng. Thật may mắn cho anh là ngoài An ra không ai mua cả, nên An có thể tự do chọn mua món hàng nào trước mà không sợ món hàng bị mua mất. Tuy nhiên, An vẫn là người chi tiêu hợp lý, anh muốn mua hết tất cả món hàng với số tiền bỏ ra là ít nhất. Hãy tính số tiền nhỏ nhất mà An bỏ ra để mua hết tất cả món hàng. Dữ liệu vào: Cho trong file văn bản có tên SALE.INP có cấu trúc: Dòng 1: Chứa 2 số nguyên dương N và K (1 ≤ N ≤ 3000; 1 ≤ K ≤ N ). Dòng 2: Chứa N số nguyên dương Ai là giá tiền của món hàng thứ i (1 ≤ Ai ≤ 109 ). (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 SALE.OUT với cấu trúc: Dòng 1: Ghi số tiền nhỏ nhất mà An phải trả để mua hết tất cả các món hàng. Ví dụ: SALE.INP SALE.OUT 5 2 10 1 3 2 4 3 Trang 1
Giải thích: An chọn mua các món hàng theo vị trí lần lượt là: 5,4,3,2,1 với giá tiền mua từng món hàng lần lượt là: 2,2,2,3,1. Tổng giá tiền Anh phải trả là 10. Câu 2. Chuỗi ốc (7 điểm). Biển Nhật Lệ TP Đồng Hới được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức những loại hình dịch vụ giải trí nghỉ dưỡng câu cá, lướt ván, lặn, ngắm san hô… Trong một đợt đi du lịch ở TP Đồng Hới, sáng sớm Đông thường đi dạo dọc bờ biển Nhật Lệ và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của Đông như sau: Ban đầu chuỗi ốc rỗng, không có vỏ ốc, khi gặp một vỏ ốc mới có thể lấy để xâu vào 1 trong hai đầu của chuỗi hoặc bỏ đi không lấy, cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu đến cuối chuỗi các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt. Yêu cầu: Cho trước dãy a1, a2,…,aN là kích thước các vỏ ốc mà Đông lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được nhiều vỏ ốc nhất. Dữ liệu vào: Cho trong file văn bản có tên SEASNAIL.INP có cấu trúc: Dòng 1: Chứa số nguyên dương N (N≤105). Dòng 2: Chứa N số nguyên dương a1, a2,…,aN (ai≤109). (Các số được ghi cách nhau ít nhất 1 dấu cách) Dữ liệu ra: Ghi vào file văn bản có tên SEASNAIL.OUT với cấu trúc. Dòng 1: Ghi một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được: Ví dụ: SEASNAIL.INP SEASNAIL.OUT 5 4 4 4 5 3 1 Câu: 3. Đường truyền quan trọng (7 điểm). Cho một mạng gồm tập hợp các nút và tập các đường truyền trực tiếp hai chiều nối giữa các cặp nút trong mạng. Người ta biết rằng mạng này thông suốt, tức là mọi cặp nút trong mạng đều có thể truyền tin cho nhau. Một số nút trong mạng cung cấp dịch vụ A còn một số nút khác cung cấp dịch vụ B cho tất cả các nút (kể cả nó). Có thể có một nút cung cấp cả hai dịch vụ. Nếu một đường truyền trực tiếp bị hỏng có thể làm cho một số nút trong mạng không thể sử dụng một trong hai dịch vụ. Các đường truyền như vậy được gọi là các đường truyền quan trọng. Bạn hãy viết chương trình xác định số lượng đường truyền quan trọng trong mạng. Dữ liệu vào: Cho trong file văn bản có tên IMPONET.INP có cấu trúc: Dòng 1: Ghi 4 số N, M, K và L. Trong đó N là số nút trong mạng, M là số đường truyền trực tiếp trong mạng, K là số nút cung cấp dịch vụ A và L là số nút cung cấp dịch vụ B. Các nút được đánh số từ 1 đến N (1≤N≤105; 1≤M≤106; 1≤K≤N; 1≤L≤N). Dòng 2: Ghi K số là số hiệu các nút cung cấp dịch vụ A. Trang 2
Dòng 3: Ghi L số là số hiệu các nút cung cấp dịch vụ B. Trong M dòng tiếp theo, mỗi dòng ghi hai số p, q thể hiện một đường truyền trực tiếp nối nút p và nút q (1≤p, q≤N, p≠q). (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 IMPONET.OUT với cấu trúc: Dòng 1: Ghi một số nguyên là số lượng đường truyền quan trọng trong mạng. Ví dụ: IMPONET.INP IMPONET.OUT Giải thích 9 10 3 4 3 Các đường truyền quan trọng 2 4 5 là: 4 9 8 3 3 2 1 2 5 6 4 1 7 9 2 3 4 2 1 5 5 6 6 7 6 8 7 9 8 7 Trang 3
SỞ GD&ĐT QUẢNG BÌNH KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA NĂM HỌC 2022 HƯỚNG DẪN CHẤM 2023 Khóa ngày 20 tháng 9 năm 2022 Môn thi: TIN HỌC BÀI THI THỨ NHẤT ́ ́ ̀ ồm có 05 trang Đap an nay g 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. Mua hàng (6 điểm). SALE.* #include #define ll long long #define v first Trang 4
#define i second using namespace std; int main(){ int n,k; long long res=0; freopen("sale.inp","r",stdin); freopen("sale.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>k; vector a(n); for (int i=0;i>a[i].v; a[i].i=i; } sort(a.begin(),a.end()); for (int i=n1;i>=0;i){ ll newprice=a[i].v; int count=0; for (int j=0;j
var i :LongInt; begin Read(f1,n); for i:=1 to n do Read(f1,A[i]); end; function Search1(i :LongInt) :LongInt; var left,right,mid :LongInt; begin left:=1; right:=res; while (leftA[i]) then left:=mid+1 else right:=mid; end; Exit(left); end; function Search2(i :LongInt) :LongInt; var left,right,mid :LongInt; begin left:=1; right:=res; while (left
F[1]:=n; L2[n]:=1; res:=1; for i:=n1 downto 1 do if (A[i]>A[F[res]]) then begin Inc(res); F[res]:=i; L2[i]:=res; end else begin j:=Search2(i); F[j]:=i; L2[i]:=j; end; end; procedure Escape; var i :LongInt; begin ans:=0; for i:=1 to n do ans:=Max(ans,L1[i]+L2[i]1); Write(g,ans); end; Begin Assign(f1,'SEASNAIL.INP'); Reset(f1); Assign(g,'SEASNAIL.OUT'); Rewrite(g); Enter; Optimize; Escape; Close(f1); Close(g); End. Câu 3. Đường truyền quan trọng (7 điểm). IMPONET.* #include #define maxn 100001 #define maxm 1000001 #define mp make_pair #define ft first #define sc second using namespace std; typedef pair II; int n,m,K,L, a[maxn], b[maxn]; II e[maxm]; int deg[maxn]; vector g[maxn]; int sla[maxn], slb[maxn]; int sn, s[maxn], cl[maxn], p[maxn], prev1[maxn]; int id, num[maxn], low[maxn]; Trang 7
int cur[maxn]; void dfs(int xp) { sn=0; s[++sn]=xp, cl[xp]=1, p[xp]=0, prev1[xp]=0; num[xp]=low[xp]=++id; sla[xp]=(a[xp]==1) ? 1 : 0; slb[xp]=(b[xp]==1) ? 1 : 0; while (sn) { int u=s[sn]; if (cur[u]
e[i]=mp(u,v); } for(int i=1;i