onthicaptoc.com
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH QUẢNG NAM
ĐỀ CHÍNH THỨC
(Đề thi có 04 trang)
KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT
NĂM HỌC 2023 – 2024 ĐỢT 2
Môn thi: TIN HỌC 12
Thời gian: 150 phút (không kể thời gian giao đề)
Ngày thi: 15/3/2024
TỔNG QUAN ĐỀ THI
Bài
Tên bài
Tệp
chương trình
Tệp dữ liệu
Tệp kết quả
Thời gian
/test
Điểm
1
BOM CHÙM
BOMCHUM.*
BOMCHUM.INP
BOMCHUM.OUT
1 s
5
2
TỆP NHẬT KÝ
NHATKY.*
NHATKY.INP
NHATKY.OUT
1 s
5
3
BỜM VÀ PHÚ ÔNG
PO.*
PO.INP
PO.OUT
1 s
5
4
KIẾN
ANT.*
ANT.INP
ANT.OUT
1 s
5
Dấu * được thay thế bởi pas hoặc cpp, … của ngôn ngữ lập trình 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. BOM CHÙM
Hiện nay, cuộc chiến giữa hai nước RU và UC ngày càng khốc liệt. Nước RU sử dụng những quả bom chùm có khối lượng lên đến đơn vị khối lượng, có sức mạnh công phá bằng tổng của các ước nguyên dương của nó. Nước UC muốn bảo vệ đất nước của mình thì với mỗi quả bom chùm của RU bắn ra phải đối kháng lại bằng quả bom có sức công phá tương đương.
Bạn là người lập trình, hãy thống kê lại với q quả bom chùm khối lượng lần lượt: a1, a2, …, aq sẽ có sức công phá tương ứng là bao nhiêu nhé!
Dữ liệu: Vào từ tệp văn bản BOMCHUM.INP gồm:
* Dòng thứ nhất chứa duy nhất số nguyên dương q (6).
* Dòng thứ hai chứa q số nguyên dương: a1, a2,…, aq, số thứ i có khối lượng là ai
.
Kết quả: Ghi ra tệp văn bản BOMCHUM.OUT gồm q số, số thứ i thể hiện sức mạnh công phá của quả bom có khối lượng ai. Các số in ra phân cách nhau bởi một dấu cách.
Ví dụ:
BOMCHUM.INP
BOMCHUM.OUT
4
2 4 10 9
3 7 18 13
4
10 11 12 13
18 12 28 14
Giải thích:
Gọi G(x) là tổng các ước của x.
Test ví dụ 1 có:

Test ví dụ 2 có:
Ràng buộc:
* Subtask 1: (40% số điểm): 4i3
* Subtask 2: (40% số điểm): 45i6
* Subtask 3: (20% số điểm):
56i 12i+1i
Bài 2. TỆP NHẬT KÝ
An lưu trên máy tính một tệp nhật ký, là một chuỗi gồm N sự kiện được ghi lại. Mỗi sự kiện được thể hiện bởi một số nguyên mà chỉ có An mới biết được ý nghĩa của nó. Bảo mật độ K của tệp nhật ký là số cặp số nguyên trong chuỗi sự kiện có tổng bằng K.
Thật không may máy tính của An bị vi rút xâm nhập và tệp nhật ký đã bị nhiễm vi rút. Chuỗi sự kiện đã bị thay đổi bởi những chữ cái La tinh in thường và dấu cách được chèn vào giữa các sự kiện. Hệ điều hành của máy tính An nhận diện được vi rút và cảnh báo một mã lỗi là một số nguyên S (|S| ≤ 109). An hiểu được, muốn khôi phục lại tệp nhật ký ban đầu cần phải xác định độ bảo mật độ S của tệp nhật ký đó.
Yêu cầu: Với tệp bị nhiễm vi rút nói trên, nhiệm vụ của bạn là giúp An xác định được độ bảo mật của tệp nhật ký để An có thể khôi phục lại dữ liệu của mình.
Dữ liệu: Vào từ tệp văn bản NHATKY.INP gồm:
* Dòng đầu là một số nguyên dương N (N ≤ 106).
* Dòng thứ hai là xâu kí tự thể hiện tệp nhật ký bị nhiễm vi rút, gồm các chữ cái La tinh in thường và dấu cách được chèn vào giữa các sự kiện.
* Dòng thứ ba gồm một số nguyên S là mã lỗi mà hệ điều hành thông báo.
Các số nguyên thể hiện cho các sự kiện có có giá trị tuyệt đối không quá 109.
Kết quả: Ghi ra tệp văn bản NHATKY.OUT gồm một số nguyên là độ bảo mật độ S của tệp nhật ký.
Ví dụ:
NHATKY.INP
NHATKY.OUT
GIẢI THÍCH
8
5ab2c5xy3 4a3c13d-6
7
5
Các cặp có tổng bằng 7 là (5,2), (2,5), (3,4), (4,3), (13, -6)
Vậy bảo mật độ 7 của tệp nhật ký là 5
Ràng buộc:
* Subtask 1: Có 30% số test tương ứng với 30% số điểm có 100 < N ≤ 104, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
* Subtask 2: Có 20% số test tương ứng với 20% số điểm có 104 < N ≤ 105, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
* Subtask 3: Có 30% số test tương ứng với 30% số điểm có 2 ≤ N ≤ 100 và không có ràng buộc gì thêm.
* Subtask 4: Có 20% số test tương ứng với 20% số điểm có 105 < N ≤ 106 và không có ràng buộc gì thêm.
Bài 3. BỜM VÀ PHÚ ÔNG
Sau khi Bờm đáp ứng hết các điều kiện mà Phú Ông đưa ra, Bờm lại thắng cuộc một lần nữa. Vì phần thưởng lần này quá lớn nên Bờm vội chạy về và lục soát khắp nhà mới tìm được một cái ba lô có sức chứa trọng lượng không vượt quá S. Bờm vội vã mang đến nhà Phú Ông nhận thưởng. Phú Ông có N thỏi vàng có trọng lượng lần lượt là a1, a2, …, aN để cho Bờm lựa chọn. Bờm rất cẩn thận lựa chọn các thỏi vàng cho vào ba lô sao cho tổng trọng lượng lớn nhất mà không vượt quá sức chứa của nó.
Yêu cầu: Bạn hãy tính toán giúp Bờm có thể chọn những thỏi vàng để tổng trọng lượng là lớn nhất và đếm có bao nhiêu cách lựa chọn như vậy? (Hai cách chọn là khác nhau nếu khác nhau ít nhất một thỏi vàng).
Dữ liệu: Vào từ tệp văn bản PO.INP có cấu trúc như sau:
* Dòng đầu gồm 2 số nguyên N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N ´ S ≤ 5 ´ 106);
* Dòng thứ hai chứa số nguyên dương Q là loại truy vấn nhận giá trị 1 hoặc 2;
* Dòng cuối gồm N số nguyên ai (0 < i3
Kết quả: Đưa ra tệp văn bản PO.OUT có cấu trúc như sau:
* Với Q = 1 thì chỉ ghi ra tổng trọng lượng lớn nhất có thể.
* Với Q = 2 thì ghi ra 2 dòng:
+ Dòng 1 ghi tổng trọng lượng lớn nhất có thể.
+ Dòng 2 ghi số cách Bờm có thể lựa chọn để đạt tổng trọng lượng lớn nhất chia lấy dư cho 109+7.
Ví dụ:
PO.INP
PO.OUT
PO.INP
PO.OUT
3 4
1
3 1 4
4
3 7
2
4 6 2
6
2

Ràng buộc:
* Có 60% test ứng với 60% số điểm có S ≤ 1000.
(40% test ứng với 40% điểm có Q=1, 60% test ứng với 60% điểm có Q=2).
Bài 4. KIẾN
Một khu vườn được xem xét như là một lưới các ô vuông, có một tổ kiến ở ô có tọa độ (0,0) và có một số ô trên lưới có vật cản. Một chú kiến muốn đi tìm thức ăn, kiến sẽ đi theo quy tắc sau:
* Từ một ô kiến có thể đi sang được 4 ô chung cạnh.
* Kiến không đi vào ô có vật cản
* Kiến không đi xa tổ quá S bước
Yêu cầu: Cho tọa độ các ô có vật cản và số S, hỏi kiến có thể đến được tất cả bao nhiêu ô.
Dữ liệu: Vào từ tệp văn bản ANT.INP gồm:
* Dòng đầu là 2 số nguyên C (số ô có vật cản) và S (0 ≤ C ≤ 10000; 1 ≤ S ≤ 107).
* C dòng sau, mỗi dòng 2 số nguyên xi , yi là tọa độ của các ô chứa vật cản.
(|xi |, |yi| < 1001).
Kết quả: Ghi ra tệp ANT.OUT gồm dòng duy nhất là số ô mà kiến có thể đến được.
Ví dụ:
ANT.INP
ANT.OUT
HÌNH MÔ TẢ CHO VÍ DỤ
4 5
-1 1
0 -1
0 1
1 0
26
1
0
Tổ
-1
-1
0
1
Ràng buộc:
* Subtask1: Có 70% số test ứng với 70% số điểm có S ≤ 103.
* Subtask2: Có 30% số test ứng với 30% số điểm có 103 < S ≤ 107.
-------------- HẾT --------------
(Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm).
Họ và tên thí sinh: ; Số báo danh:
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH QUẢNG NAM
KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT
NĂM HỌC 2023-2024 ĐỢT 2
HDC CHÍNH THỨC
HƯỚNG DẪN CHẤM MÔN TIN HỌC LỚP 12

(Bản hướng dẫn này gồm 01 trang)
Bài thi chấm bằng test, và chấm bằng phần mềm Themis kèm theo
(mới nhất của thầy Lê Minh Hoàng và Đỗ Đức Đông)
Bài 1 (5,0 điểm) gồm có 25 test, mỗi test 0,2 điểm, thời gian 1s, bộ nhớ 1024 MB
* Có 40% test tương ứng 40% số điểm với 4i3
* Có 40% test tương ứng 40% số điểm với 45i6
* Có 20% test tương ứng 20% số điểm với
56i 12i+1i
Bài 2 (5,0 điểm) gồm có 40 test, mỗi test 0,125 điểm, thời gian 1s, bộ nhớ 1024 MB
* Có 30% số test tương ứng với 30% số điểm có 100 < N ≤ 104, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
* Có 20% số test tương ứng với 20% số điểm có 104 < N ≤ 105, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
* Có 30% số test tương ứng với 30% số điểm có 2 ≤ N ≤ 100 và không có ràng buộc gì thêm.
* Có 20% số test tương ứng với 20% số điểm có 105 < N ≤ 106 và không có ràng buộc gì thêm.
Bài 3 (5,0 điểm) gồm có 20 test, mỗi test 0,25 điểm, thời gian 1s, bộ nhớ 1024 MB
* Có 60% test tương ứng với 60% số điểm có S ≤ 1000.
(40% test ứng với 40% điểm có Q=1, 60% test ứng với 60% điểm có Q=2).
Bài 4 (5,0 điểm) gồm có 20 test, mỗi test 0,25 điểm, thời gian 1s, bộ nhớ 1024 MB
* Có 70% số test ứng với 70% số điểm có S ≤ 103.
* Có 30% số test ứng với 30% số điểm có 103 < S ≤ 107.
---------------HẾT ---------------
onthicaptoc.com

onthicaptoc.com De thi HSG Tin 12 Quang Nam 23 24