Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2022 - Tin học - Khối 10

Toán học đóng vai trò quan trọng trong Tin học. Khi thiết kế chương trình giảng dạy môn Tin học cho các lớp chuyên Tin theo chương trình giáo dục phổ thông mới (Chương trình giáo dục phổ thông 2018), thầy chủ biên chương trình Hồ Sĩ Đàm đã rất chú trọng nội dung toán. Chuyên đề đầu tiên mà học sinh sẽ học sau khi học xong ngôn ngữ lập trình là chuyên đề “Số học và tổ hợp”. Tham gia kì thi Duyên Hải năm 2022, thầy Hồ Sĩ Đàm đã ra một bài toán như sau:

Cho số nguyên dương \(n\) và hai số nguyên không âm \(a\) , \(b\) kí hiệu \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\) (làm tròn xuống), hãy tính:

Input

• Gồm 1 dòng chứa ba số nguyên \(n, a, b\).

Output

• In ra một số nguyên là tổng \(S\) chia dư cho \((10^{9} + 7)\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 100; a, b \leq 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{12}; a = 1; b = 0\)
• Subtask \(3\) (\(30\%\) số điểm): \(n, a, b \leq 10^{12}\)

Example

3 1 2

12

Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm \(m\) hàng và \(n\) cột, các hàng được đánh số từ trên xuống dưới từ \(1\) đến \(m\), các cột được đánh số từ trái sang phải từ \(1\) đến \(n\), ô nằm giao giữa hàng \(i\) (\(1 \leq i \leq m\)) và cột \(j\) (\(1 \leq j \leq n\)) gọi là ô \((i, j)\) và có giá trị ban đầu là \(a_{ij}\). Cần thực hiện \(Q\) thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

• Thao tác loại \(1\) có dạng: \(1 \ x \ y \ u \ v \ w\) có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\) sẽ được cộng thêm \(w\);
• Thao tác loại \(2\) có dạng: \(2 \ x \ y \ u \ v\) có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\).

Input

• Dòng đầu chứa ba số nguyên dương \(m\), \(n\), \(Q\) (\(m, n \leq 500\));
• Dòng thứ \(i\) (\(1 \leq i \leq m\)) trong \(m\) dòng sau chứa \(n\) số nguyên không âm \(a_{i1}, a_{i2}, \ldots, a_{in}\) (\(a_{ij} \leq 10 ^ 9\)).
• Dòng thứ \(k\) (\(1 \leq k \leq Q\)) trong \(Q\) dòng sau mô tả thao tác thứ \(k\). Nếu là thao tác loại \(1\), dòng gồm năm số nguyên \(1\), \(x\), \(y\), \(u\), \(v\), \(w\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\); \(0 \leq w \leq 10 ^ 9\)), nếu là thao tác loại \(2\), dòng gồm bốn số nguyên \(2\), \(x\), \(y\), \(u\), \(v\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\)).

Output

• Ghi ra thiết bị chuẩn một số dòng, mỗi dòng tương ứng là câu trả lời cho thao tác loại \(2\) lần lượt xuất hiện trong file dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \leq 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(Q \leq 10 ^ 5\) và tất cả thao tác loại \(1\) xuất hiện trước các thao tác loại \(2\);
• Subtask \(3\) (\(20\%\) số điểm): \(Q \leq 10 ^ 4\);
• Subtask \(4\) (\(20\%\) số điểm): \(Q \leq 10 ^ 5\).

Example

2 3 3
0 0 0
0 0 0
2 1 1 2 3
1 1 1 2 3 1
2 1 1 2 2      

0
4        

Bài toán dưới đây có rất nhiều cách tiếp cận, bài toán rất phù hợp để giảng dạy và kiểm tra về nội dung các chiến lược phân tích thiết kế thuật toán, bài toán như sau:
Có \(n\) hộp bi xếp thành một hàng, hộp thứ \(i (1\le i\le n)\) có \(a_{i} (0\le a_i\le 10^9)\) viên \(b_{i}\). Mỗi lượt, người chơi được chọn một đoạn gồm các hộp bi liên tiếp vẫn còn bi và lấy ra từ mỗi hộp một viên bi. Người chơi được thực hiện không quá r lượt và mong muốn làm cho nhiều hộp rỗng nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n,r\);
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1},a_{2},…,a_{n}\).

Output

• Ghi ra file thiết bị ra chuẩn một số nguyên là số lượng hộp rỗng nhiều nhất đạt được nếu người chơi biết chiến lược chơi tối ưu.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\le 10, r=1\);
• Subtask \(2\) (\(30\%\) số điểm): \(n\le 10, r\le 5\);
• Subtask \(3\) (\(30\%\) số điểm): \(n\le 200, r\le 200\);
• Subtask \(4\) (\(20\%\) số điểm):\(n\le 200, r\le 10^9\);
• Subtask \(5\) (\(10\%\) số điểm): \(n\le 2000, r\le 10^9\).

Example

6 2
0 2 1 2 2 3

4