SỞ GD & ĐT NGHỆ AN TRƯỜNG THPT ĐÔ LƯƠNG 1           ĐỀ CHÍNH THỨC

ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG TỈNH BẬC THPT- LỚP 12 NĂM HỌC 2023 – 2024 Môn: TIN HỌC Thời gian làm bài: 150 phút (không kể thời gian giao đề)

 TỔNG QUAN BÀI THI

Tên bài	File nguồn	File Input	File Output	Bộ nhớ tối đa	Thời gian
TRUY VẤN TỔNG	QSUM.*	QSUM.INP	QSUM.OUT	1024Mb	1 giây
BÌNH CHỌN QUA ĐIỆN THOẠI	CPHONE.*	CPHONE.INP	CPHONE.OUT	1024Mb	1 giây
XÂU CON	SUBSTR.*	SUBSTR.INP	SUBSTR.OUT	1024Mb	1 giây
TÚI BA GANG	CAYKHE.*	CAYKHE.INP	CAYKHE.OUT	1024Mb	1 giây

Phần mở rộng .* được thay thế bằng Pas, cpp, Py ứng với các ngôn ngữ lập trình Pascal, C++, Python.

HÃY LẬP TRÌNH GIẢI CÁC BÀI TOÁN SAU:

Câu 1. (6.0 điểm) .   TRUY VẤN TỔNG                                            

Cho một dãy số nguyên gồm N phần tử nguyên A₁, A₂, …, A_N.

Yêu cầu: Hãy trả lời Q truy vấn có dạng:

– i j: tính tổng các phần tử liên tiếp thuộc đoạn từ i đến j.

INPUT: QSUM.INP

• Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ 10⁵)
• Dòng thứ 2 chứa N số nguyên A₁, A₂, …, A_N (|A_i| ≤ 10³)
• Q dòng tiếp theo mỗi dòng chứa hai số nguyên i, j (1 ≤ i ≤ j ≤ N) thể hiện một câu hỏi truy vấn.

OUTPUT: QSUM.OUT

• Chứa Q dòng, mỗi dòng là câu trả lời truy vấn tương ứng trong INPUT.

 Ví dụ:

QSUM.INP	QSUM.OUT	Giải thích ví dụ
5 3 1 3 -4 5 -2 1 4 2 5 3 3	5 2 -4	Dãy có 5 phần tử và 3 truy vấn – Truy vấn 1: tính tổng các phần từ thứ 1 đến thứ 4 là:  1 + 3 + (-4) + 5 = 5 – Tương tự như vậy ta được kết quả của 2 truy vấn còn lại là 2 và -4

    Giới hạn:

          – Có 80% số test với dữ liệu cho là: 1 ≤ N, Q ≤ 5000.

Câu 2. (5.0 điểm)   BÌNH CHỌN QUA ĐIỆN THOẠI

 Trong vòng chung kết cuộc thi “Vietnam Next Top Model” trên VTV3 các thí sinh được đánh số báo danh là một số nguyên dương có giá trị không vượt quá 1000. Khán giả xem truyền hình có thể bình chọn cho thí sinh mình yêu thích bằng cách nhắn tin qua điện thoại di động. Ban tổ chức nhận được tin nhắn hợp lệ của N khán giả (các khán giả được đánh số từ 1 đến N), khán giả thứ i bình chọn cho thí sinh mang số báo danh ai.Hãy liệt kê số báo danh của những thí sinh được nhiều khán giả bình chọn nhất theo thứ tự tăng dần.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên dương N là số lượng khán giả có tin nhắn bình chọn hợp lệ (N ≤ 10⁵)
• N dòng tiếp theo, dòng thứ i ghi số nguyên dương a_i là số báo danh của thí sinh mà khán giả thứ i bình chọn.

Kết quả:

• Danh sách các thí sinh được nhiều khán giả bình chọn nhất theo thứ tự số báo danh tăng dần

Ví dụ:

CPHONE.INPUT	CPHONE.OUTPUT
5 3 1 3 2 2	2 3

Giới hạn:

Có ít nhất 50% số điểm của bài tương ứng với các test có N≤1000.

Câu 3. (5 điểm)     XÂU CON                     

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự “0” hoặc “1”.

Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.

Yêu cầu: Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng k ký tự “1”.

Dữ liệu vào: SUBSTR.INP

• Dòng 1: chứa một số nguyên k (0 ≤ k ≤ 10⁶)
• Dòng 2: chứa một xâu nhị phân có độ dài ≤ 10⁶

Dữ liệu ra: SUBSTR.OUT

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ

SUBSTR.INP	SUBSTR.OUT
2 01010	4

Giải thích: có 4 xâu con chứa 2 ký tự 1 là: “101”, “0101”, “1010”, “01010”

Giới hạn : gọi n là độ dài xâu​

          – Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.

          – Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.

          – Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 1.000.000.

Câu 4. (4 điểm).   TÚI BA GANG    

Trong truyện cổ tích “Cây Khế” ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu báu. Người em băn khoăn không biết chọn đồ vật nào cho vào túi vì chỉ có một cái túi ba gang..

Giả sử rằng trên hòn đảo kia có N đồ vật khác nhau, đồ vật thứ i có giá trị là a_i và có thể tích là b_i. Cũng giả sử rằng cái túi mà người em mang đi chỉ có thể tích là M. Bạn hãy giúp người em chọn ra trong N đồ vật trên một số đồ vật sao cho tổng thể tích của các đồ vật được chọn không vượt quá M và tổng giá trị các đồ vật được chọn là lớn nhất.

Input: Cho trong file văn bản CAYKHE.INP

• Dòng đầu tiên ghi hai số N, M (N,M≤100)
• N dòng tiếp theo, dòng thứ i ghi hai số a_i và b_i lần lượt là giá trị và thể tích của đồ vật thứ i (a_i, b_i≤100)

Output: Ghi ra file văn bản CAYKHE.OUT

• Dòng đầu tiên ghi tổng giá trị lớn nhất có thể cho vào trong túi
• Dòng thứ hai ghi số hiệu các đồ vật được cho vào trong túi. Đầu tiên ghi K là số lượng đồ vật được chọn, tiếp theo là K số thể hiện số hiệu các đồ vật được chọn.

Ví dụ:

CAYKHE.INP	CAYKHE.OUT
5 10 20 3 19 1 30 7 24 3 15 6	63 3 1 2 4

—————————HẾT—————————

Họ và tên thí sinh: ……………………………………..…… Số báo danh:…………………

Tham khảo code và bộ test tại đây: https://drive.google.com/drive/folders/1ya5c2xu9Ad5Bj4yVVjDV5M22NSjOaYOL?usp=sharing

https://drive.google.com/drive/folders/1ya5c2xu9Ad5Bj4yVVjDV5M22NSjOaYOL?usp=sharing