Đề Thi Học Sinh Giỏi Môn Tin 10 Sở GD Quảng Nam 2021-2022 Có Đáp Án

Trang 1/4

SỞ GIÁO DỤC VÀ ĐÀO TẠO

TỈNH QUẢNG NAM

(Đề thi có 04 trang)

KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT

NĂM HỌC 2021 - 2022 Môn thi : TIN HỌC 10 (CHUYÊN) Thời gian : 180 phút (không kể thời gian giao đề) Ngày thi : 22/03/2022

TỔNG QUAN ĐỀ THI

Bài Tên bài File chương

trình File dữ liệu vào File kết quả Thời

gian 1 Số nguyên tố SNT.* SNT.INP SNT.OUT 1 s

2 Xếp sách THUVIEN.* THUVIEN.INP THUVIEN.OUT 1 s 3 Đếm cặp DEMCAP.* DEMCAP.INP DEMCAP.OUT 1 s

4 Mạng xã hội MANGXH.* MANGXH.INP MANGXH.OUT 1 s

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++.

Hãy lập trình giải các bài toán sau:

Bài 1. (5 điểm) Số nguyên tố

Số nguyên tố là số nguyên dương chỉ có hai ước khác nhau là 1 và chính nó.

Ví dụ: 2, 3, 5, 7, 11, … là các số nguyên tố.

Yêu cầu: Tính trung bình cộng các số nguyên tố trong một đoạn [A, B] cho trước.

Dữ liệu vào: Từ tệp văn bản SNT.INP gồm:

 Dòng đầu ghi số nguyên dương N là số lượng đoạn cần tính (N ≤ 10);  N dòng tiếp theo, mỗi dòng ghi thông tin của một đoạn cần tính gồm hai số nguyên dương

A và B cách nhau một dấu cách (A < B).

Kết quả: Đưa ra tệp văn bản SNT.OUT gồm N dòng, mỗi dòng chứa kết quả là phần nguyên của giá trị trung bình cộng cần tìm.

Ví dụ:

SNT.INP SNT.OUT

2

1 10

10 20

4

15

ĐỀ CHÍNH THỨC

Trang 2/4

Giới hạn:

 Có 50% test tương ứng 50% số điểm của bài với B ≤ 103;

 Có 30% test tương ứng 30% số điểm của bài với B ≤ 104;

 Có 20% test tương ứng 20% số điểm còn lại của bài với B ≤ 106.

Bài 2. (5 điểm) Xếp sách

Trên một kệ sách của một thư viện có N quyển sách được đánh số từ trái qua phải, lần lượt từ 1 đến N. Sau một thời gian cho độc giả mượn đọc tại chỗ, các quyển sách vẫn được đặt trên kệ nhưng thứ tự các quyển sách bị đảo lộn. Người quản lý thư viện cần sắp xếp lại các quyển sách theo đúng thứ tự ban đầu từ 1 đến N. Một bước di chuyển là một lần rút ra một quyển sách và chèn vào một vị trí bất kỳ trên kệ.

Yêu cầu: Hãy giúp người quản lý tìm phương án sắp xếp với số lần chuyển là ít nhất để sắp xếp N quyển sách này theo đúng thứ tự từ 1 đến N từ trái sang phải.

Dữ liệu vào: Từ tệp văn bản THUVIEN.INP gồm:

 Dòng đầu gồm một số nguyên dương N (1 ≤ N ≤ 105);  Dòng thứ hai gồm N số nguyên dương (mỗi số cách nhau một dấu cách).

Kết quả: Ghi ra tệp văn bản THUVIEN.OUT gồm một số duy nhất là số lần chuyển sách để N quyển sách về đúng thứ tự ban đầu.

Ví dụ:

THUVIEN.INP THUVIEN.OUT

3

3 1 2

1

Giới hạn:

 Có 40% test tương ứng 40% số điểm của bài với N ≤ 103;

 Có 40% test tương ứng 40% số điểm của bài với N ≤ 5×104;

 Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 105.

Bài 3. (5 điểm) Đếm cặp

Cho dãy số nguyên gồm N phần tử a1, a2,…, aN. Gọi tổng các phần tử liên tiếp là:

T[L,R]= ∑ ?? ? ?=? (với 1 ≤?< ?≤?).

Yêu cầu: Với dãy số đã cho, hãy đếm xem có bao nhiêu cặp (L,R) sao cho T[L,R]=0.

Dữ liệu vào: Từ tệp văn bản DEMCAP.INP gồm:

 Dòng đầu tiên chứa số tự nhiên N (1 ≤ N ≤ 105);

Trang 3/4

 Dòng tiếp theo chứa dãy số nguyên gồm N phần tử a1, a2,…, aN ( |ai | ≤ 109) các số cách

nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản DEMCAP.OUT gồm một số duy nhất là kết quả cần tìm.

Ví dụ:

DEMCAP.INP DEMCAP.OUT

5

1 -2 3 -1 -1

2

Giới hạn:

 Có 60% test tương ứng 60% số điểm của bài với N ≤ 102;

 Có 20% test tương ứng 20% số điểm của bài với N ≤ 104;

 Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 105.

Bài 4. (5 điểm) Mạng xã hội

Ngày nay mạng xã hội đã trở nên phổ biến, nhờ mạng xã hội mà chúng ta có thể kết bạn, trao đổi, chia sẻ thông tin, theo dõi, … với nhiều người. Là học sinh, An cũng đã tham gia vào nhiều mạng xã hội khác nhau như Facebook, Zalo,… An thường xuyên sử dụng hằng ngày để trao đổi thông tin với bạn bè trong học tập và các công việc khác.

Một hôm trên đường đi học về An nhặt được một chiếc ví, trong đó chỉ có tiền và một số vật dụng cá nhân mà không có thông tin gì về chủ nhân của nó. Để tìm và trả lại người đánh mất, An đã đưa …