HSG lớp 9 Quảng Ninh 2022-2023 (Bảng A)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THCS TỈNH QUẢNG NINH Năm học 2022 - 2023

MÔN TIN HỌC - BẢNG A Ngày thi: 14/03/2023
Thời gian: 150 phút

---

Tổng quan đề thi

Bài	Tên bài	File CT	File input	File output	Điểm
1	Màn hình	DISP.*	DISP.INP	DISP.OUT	6
2	Dãy số tăng	INCR.*	INCR.INP	INCR.OUT	6
3	Bánh mì và bánh rán	DONU.*	DONU.INP	DONU.OUT	5
4	Giờ học giáo dục thể chất	PHYS.*	PHYS.INP	PHYS.OUT	3

(* là pas, cpp hoặc py)

Bài 1. Màn hình (6 điểm)

Một công ty lớn đã quyết định đưa ra một loại màn hình có đúng n điểm ảnh được xếp thành các hàng và các cột.

Nhiệm vụ của bạn là xác định số hàng điểm ảnh a và số cột điểm ảnh b sao cho:

• Có đúng n điểm ảnh trên màn hình, tức là a × b = n;
• Số hàng điểm ảnh không vượt quá số cột điểm ảnh, tức là a ≤ b;
• Sự khác biệt b − a càng nhỏ càng tốt.

Dữ liệu: Vào từ tệp văn bản DISP.INP gồm một dòng chứa số nguyên n (1 ≤ n ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản DISP.OUT hai số nguyên tương ứng là số hàng và số cột điểm ảnh cần tìm của màn hình.

Ví dụ:

DISP.INP	DISP.OUT
8	2 4
25	5 5

Ràng buộc:

• Có 30% số test ứng với 30% số điểm thỏa mãn: 1 ≤ n ≤ 10³;
• 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ n ≤ 10⁷;
• 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Bài 2. Dãy số tăng (6 điểm)

Dãy số a₁, a₂, …, aₙ được gọi là tăng nếu a₁ < a₂ < … < aₙ.

Bạn được cho một dãy số b₁, b₂, …, bₙ và một số nguyên dương d. Trong mỗi lần thao tác, bạn chọn một phần tử của dãy số và cộng thêm d vào nó. Số thao tác ít nhất là bao nhiêu để biến đổi dãy số đã cho trở thành dãy số tăng.

Dữ liệu: Vào từ tệp văn bản INCR.INP:

• Dòng đầu tiên chứa hai số nguyên n và d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹).
• Dòng thứ hai chứa n số nguyên tương ứng là dãy số b₁, b₂, …, bₙ (1 ≤ bᵢ ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản INCR.OUT một số nguyên là số thao tác ít nhất để biến đổi dãy số đã cho trở thành dãy số tăng.

Ví dụ:

INCR.INP	INCR.OUT
4 2 1 3 3 2	3

Trong ví dụ trên, ta có dãy số b là: 1, 3, 3, 2 và d = 2. Số thao tác ít nhất để biến đổi dãy số trở thành dãy số tăng là 3 và một trong các cách thực hiện như sau:

• Thao tác thứ nhất: Cộng thêm d vào phần tử thứ ba, dãy số trở thành: 1, 3, 5, 2;
• Thao tác thứ hai: Cộng thêm d vào phần tử thứ tư, dãy số trở thành: 1, 3, 5, 4;
• Thao tác thứ ba: Cộng thêm d vào phần tử thứ tư, dãy số trở thành: 1, 3, 5, 6 và là dãy số tăng.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm thỏa mãn: 1 ≤ n, d, bᵢ ≤ 10²;
• 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ n ≤ 10³ và 1 ≤ d, bᵢ ≤ 10⁶;
• 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Bài 3. Bánh mì và bánh rán (5 điểm)

Mẹ của An đã lên kế hoạch ăn sáng bằng bánh mì hoặc bánh rán cho An trong n ngày (được đánh số từ 1 đến n). Mẹ của An viết một xâu s độ dài n, trong đó kí tự thứ i (1 ≤ i ≤ n) là ‘0’ hoặc ‘1’ biểu thị ngày thứ i sẽ ăn bánh mì hoặc bánh rán tương ứng.

An thích ăn bánh rán hơn bánh mì, nên anh ta muốn chọn một đoạn gồm k ký tự liên tiếp trong xâu s và thay đổi mỗi kí tự ‘0’ trong đoạn này thành ‘1’. Gọi time là số ngày liên tiếp dài nhất mà An ăn bánh rán. Bạn hãy giúp An tìm giá trị time lớn nhất mà anh ta có thể đạt được bằng cách chọn một đoạn hợp lý.

Dữ liệu: Vào từ tệp văn bản DONU.INP:

• Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 10⁶).
• Dòng thứ hai chứa xâu s độ dài n, chỉ gồm các ký tự ‘0’ và ‘1’.

Kết quả: Ghi ra tệp văn bản DONU.OUT một số nguyên là giá trị time lớn nhất.

Ví dụ:

DONU.INP	DONU.OUT
13 2 0101110000101	5
6 3 100001	4

• Trong ví dụ thứ nhất, An cần chọn đoạn ký tự từ thứ 2 đến thứ 3 là “10”, sau đó thay đổi kí tự thứ 3 trong s thành “1” và time là 5 ngày*: từ ngày thứ 2 đến ngày thứ 6.*
• Trong ví dụ thứ hai, An cần chọn đoạn ký tự từ thứ 2 đến thứ 4 là “000”, sau đó thay đổi tất cả các kí tự trong đoạn này từ “0” thành ‘1’ và time là 4 ngày: từ ngày thứ 1 đến ngày thứ 4.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm thỏa mãn: 1 ≤ k < n ≤ 10²;
• 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ k ≤ n ≤ 10³;
• 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Bài 4. Giờ học giáo dục thể chất (3 điểm)

Trước giờ học giáo dục thể chất, một lớp gồm n học sinh xếp thành một hàng. Tất cả học sinh trong lớp đều có chiều cao khác nhau. Vị trí thứ i (i = 1, 2, …, n) tính từ đầu bên trái của hàng là học sinh có chiều cao pᵢ (1 ≤ pᵢ ≤ n).

Khi bắt đầu giờ học, thầy giáo có thể thay đổi thứ tự học sinh trong hàng. Để làm điều này, thầy giáo có thể thực hiện thao tác sau đúng một lần: chọn một đoạn từ vị trí l đến vị trí r (1 ≤ l ≤ r ≤ n) và sắp xếp các học sinh trong đoạn này theo chiều cao tăng dần từ trái sang phải. Ví dụ n = 5, ban đầu học sinh theo thứ tự có chiều cao là 5, 2, 4, 1, 3 và thầy giáo chọn l = 1, r = 4 thì sau khi sắp xếp học sinh sẽ theo thứ tự có chiều cao là 1, 2, 4, 5, 3.

Sử dụng thao tác này, thầy giáo có thể sắp xếp để hai học sinh nào đó cách xa nhau nhất có thể. Khoảng cách giữa hai học sinh bằng sự chênh lệch giữa các vị trí mà hai học sinh đứng. Với mỗi cặp học sinh, thầy giáo tính khoảng cách lớn nhất giữa hai học sinh này sau khi thực hiện đúng 1 thao tác nói trên. Bạn hãy giúp thầy giáo tìm tổng của các giá trị này.

Cụ thể hơn, hãy xét hai học sinh ban đầu ở vị trí i và j (1 ≤ i < j ≤ n). Gọi d(i, j) là khoảng cách lớn nhất giữa hai học sinh đó mà thầy giáo có thể đạt được bằng cách chọn một đoạn và sắp xếp. Bạn cần tính tổng tất cả các giá trị d(i, j) với mọi i, j thỏa mãn 1 ≤ i < j ≤ n.

Dữ liệu: Vào từ tệp văn bản PHYS.INP:

• Dòng đầu tiên chứa một số nguyên n là số học sinh trong lớp (2 ≤ n ≤ 3000).
• Dòng thứ hai chứa n số nguyên p₁, p₂, …, pₙ là chiều cao của từng học sinh trong hàng (1 ≤ pᵢ ≤ n). Dữ liệu đảm bảo rằng tất cả các số pᵢ đều phân biệt.

Kết quả: Ghi ra tệp văn bản PHYS.OUT một số nguyên là câu trả lời cho bài toán.

Ví dụ:

PHYS.INP	PHYS.OUT
5 5 2 4 1 3	35
10 2 1 6 8 3 5 9 10 7 4	256
2 2 1	1

• Trong ví dụ đầu tiên, câu trả lời là tổng của các số sau: d(1,2) = 3, d(1,3) = 4, d(1,4) = 4, d(1,5) = 4, d(2,3) = 3, d(2,4) = 3, d(2,5) = 4, d(3,4) = 3, d(3,5) = 3, d(4,5) = 4.
• Ví dụ với hai học sinh ban đầu đứng ở vị trí 4 và 5, có chiều cao lần lượt là 1 và 3, thầy giáo có thể chọn đoạn với l = 1 và r = 4. Khi đó dãy học sinh sẽ thay đổi như sau: 5, 2, 4, 1, 3 → 1, 2, 4, 5, 3 (Đoạn đã chọn được gạch dưới) và khoảng cách giữa hai học sinh này là 4.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm thỏa mãn: n ≤ 10;
• 20% số test khác ứng với 20% số điểm thỏa mãn: n ≤ 50;
• 20% số test khác ứng với 20% số điểm thỏa mãn: n ≤ 100;
• 20% số test khác ứng với 20% số điểm thỏa mãn: n ≤ 600;
• 20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.