Buổi 01 - THTB Sơ loại Toàn quốc 2025 (lần 1)

Một số nguyên dương được gọi là số đẹp nếu tổng các chữ số chia hết cho \(9\). Ví dụ, số \(9, 18, 2007\) là các số đẹp.

Yêu cầu: Cho số nguyên dương \(n\), tính tổng các số đẹp không vượt quá \(n\).

Input

• Gồm một dòng chứa số nguyên \(n\) (\(n \le 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là tổng tính được.

Example

20

27

Scoring

• Có \(80\%\) số test có \(n \le 10^6\).
• Có \(20\%\) số test còn lại không có ràng buộc nào thêm.

Bảng vuông gần nguyên tố

Giả sử \(A\) là lưới ô vuông gồm \(m\) dòng và \(n\) cột. Các dòng của lưới được đánh số từ \(1\) đến \(m\), từ trên xuống dưới. Các cột của lưới được đánh số từ \(1\) đến \(n\), từ trái sang phải. Ô nằm trên giao của dòng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) của lưới gọi là ô \((i, j)\) được điền số nguyên không âm \(a_{i,j}\) (\(a_{i,j} \le 10^6\)).

Một hình vuông gồm các ô nằm trong lưới \(A\) được gọi là bảng vuông gần nguyên tố nếu có không quá một ô trong hình vuông chứa số không phải là số nguyên tố.

Yêu cầu: Cho \(m, n\) và các số được điền trên lưới \(A\), hãy tìm bảng vuông gần nguyên tố có diện tích lớn nhất.

Input

• Dòng đầu chứa hai số nguyên \(m, n\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên không âm \(a_{i,1}, a_{i,2}, \dots, a_{i,n}\).

Output

• Gồm một số nguyên là số ô trong bảng vuông gần nguyên tố tìm được.

Example

3 4
1 2 3 4
1 3 5 7
2 4 6 8

4

Ràng buộc

• Có \(25\%\) số test có \(m, n \le 10\).
• Có \(25\%\) số test khác có \(m, n \le 50\).
• Có \(25\%\) số test khác có \(m, n \le 300\).
• Có \(25\%\) số test còn lại có \(m \cdot n \le 10^6\).

Biến đổi

Cho dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(4 \le n \le 8\); \(a_i \le 10^9\)). Cần biến đổi dãy để tất cả các phần tử đều bằng \(0\). Mỗi bước được phép chọn \(4\) phần tử liên tiếp \(a, b, c, d\) biến đổi thành \(|a - b|, |b - c|, |c - d|, |d - a|\).

Ví dụ:
0 1 3 5 9
0 2 2 4 8 (1)
0 0 2 4 6 (2)
0 2 2 2 6 (3)
0 0 0 4 4 (4)
0 0 4 0 4 (5)
0 4 4 4 4 (6)
0 0 0 0 0 (7)

Yêu cầu: Hãy tính số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Input

• Gồm một số dòng, mỗi dòng chứa một số nguyên là các phần tử của dãy \(a_1, a_2, \dots, a_n\).

Output

• Ghi số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Example

0
1
3
5
9

7

Ràng buộc

• Có \(30\%\) số điểm tương ứng với \(n = 4\).
• Có \(30\%\) số điểm khác tương ứng với \(n \le 6\).
• \(40\%\) số điểm còn lại không có ràng buộc nào thêm.

Cho một hình chữ nhật có \(N\) hàng và \(M\) cột có số thứ tự được đánh từ trên xuống và từ trái sang phải.

Trên mỗi ô có viết một số nguyên và nhiệm vụ chúng ta phải trả lời \(Q\) truy vấn. Mỗi truy vấn sẽ gồm bốn số nguyên là \(x_1, y_1, x_2, y_2\), sẽ mô tả một khu vực con trong hình chữ nhật. Ứng với mỗi truy vấn, hãy in ra tổng của của khu vực con đó, có điểm \((x_1, y_1)\) là ô góc trái trên và có điểm \((x_2, y_2)\) là ô ở góc phải dưới của khu vực.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) (chiều rộng) và \(M\) (chiều dài) \((1 \leq N, M \leq 1000)\)
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên, giá trị tuyệt đối của mỗi số nguyên này không vượt quá \(10^9\)
• Dòng kế tiếp, chứa một số nguyên \(Q\) (số truy vấn) \((1 \leq Q \leq 10^5)\)
• \(Q\) dòng kết tiếp, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\). \((1 \leq x_1 \leq x_2 \leq N)\), \((1 \leq y_1 \leq y_2 \leq M)\)

Output

• In ra \(Q\) dòng, ứng với truy vấn thứ \(i\), in ra một số nguyên là tổng của khu vực hình chữ nhật được nhắc đến bởi truy vấn thứ \(i\).

Example

Test 1

Input

3 3
1 2 3
-4 -5 -6
7 8 9
4
1 1 2 3
2 3 3 3
1 1 2 2
1 1 1 3

Output

-9
3
-6
6

Note

Bé Cam hôm nay đến lớp học Toán và được cô dạy về bình phương của một số. Cô cho Cam một bảng \(A\) kích thước \(10^{6} \times 10^{6}\) phần tử. Các dòng được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ dưới lên trên, các cột được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ trái sang phải. Phần tử nằm ở hàng \(i\), cột \(j\) được kí hiệu là \(A_{ij}\) được tính bằng công thức \(A_{ij} = i^{2} + j^{2}\).

Cô giáo tạo ra dãy \(B\) đánh số từ \(1\) đến \(10^{12}\) gồm toàn bộ các phần tử của bảng \(A\) rồi sắp xếp theo thứ tự không giảm. Sau đó cô hỏi Cam xem số thứ \(K\) trong dãy \(B\) có giá trị là bao nhiêu? Lúc đầu cô đưa số \(K\) nhỏ nên Cam còn đếm được. Khi số \(K\) lớn lên, Cam không còn tính nhẩm trong đầu được nữa, Cam muốn các bạn thi Tin học trẻ hôm nay giúp bé tìm đáp án cho câu hỏi của cô giáo nhé. Hình bên là ảnh Cam chụp góc trái dưới cùng bảng \(A\).

Sau khi chuyển các phần tử của bảng \(A\) vào dãy \(B\) và sắp theo thứ tự không giảm thì Cam có những phần tử đầu tiên của dãy \(B\) là \(\{2, 5, 5, 8, 10, 10, 13, 13, 17, 17, 18, \ldots \}\) Khi cô hỏi \(K=5\) thì Cam đã ngay lập tức đưa ra được đáp án là \(10\). Các bạn hãy giúp bé với những số \(K\) lớn hơn nhé.

Input

• Một dòng duy nhất chứa một số nguyên dương \(K\) \((1 \leq K \leq 10^{12})\).

Output

• In ra một số nguyên là số thứ \(K\) trong dãy \(B\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \le K \le 10^5\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5

10

Tiền sĩ Hùng là một nhà nghiên cứu về các con số. Đề tài lần này ông được giao nhiệm vụ tìm ra một bài toán để kiểm tra năng lực của các học viên trong phòng thí nghiệm của ông. Nhưng tất cả các học viên của ông đều rất thông minh nên để thử tài họ phải là một bài toán cực khó. Con trai của ông năm nay vào lớp 3. Do ảnh hưởng của bố nên cậu ta cũng rất hứng thú với những con số. Trong khi Hùng đang nát óc nghĩ bài toán thì con trai của ông chỉ vào đống tài liệu về các dãy bit gồm toàn số \(0, 1\) và khoái chí nói rằng: “Ba ơi, đoạn bit này có \(5\) số \(0\) và \(5\) số \(1\) ba ạ. Con rất thích những thứ cân bằng như thế !!”. Cậu con trai vừa dứt lời, Hùng liền nghĩ ngay ra bài toán để thách đố học viên của mình. Quả nhiên sau đó tât cả đều chịu thua trước bài toán hóc búa này. Các bạn hãy giúp các bạn học viên giải quyết bài toán của Tiến sĩ Hùng nhé!!!! Bài toán như sau: “Cho dãy số \(A\) gồm \(N\) phần tử \(0\) hoặc \(1\). Tìm đoạn con liên tiếp dài nhất mà trong đó có số lượng số \(0\) và số lượng số \(1\) là như nhau”.

Input

• Dòng đầu tiên chứa \(1\) số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1},A_{2},...,A_{N}\).

Output

• Một dòng ghi một số nguyên duy nhất là kết quả của bài toán.

Constraints

• \(1 \leq n \leq 10^{5}\)
• \(0 \leq A_{i} \leq 1\)

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 1 0 0 1 

4

10
1 0 0 1 1 1 0 1 1 0 

6

4
1 1 1 1 

0

Lập trình liệt kê các hoán vị của \({1, 2, ... , n}\) theo thứ tự từ điển.

Input

• 1 dòng chứa số nguyên dương \(n \le 10\).

Output

• In ra các hoán vị theo thứ tự từ điển, mỗi hoán vị trên một dòng.

Example

3

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

Bạn được cho 1 danh sách \(A\) gồm \(n\) số nguyên và một số nguyên \(m\). Bạn được quyền thực hiện các thao tác thỏa mãn điều kiện sau:

• Không được thay đổi thứ tự các phần tử của danh sách này.
• Bạn phải chèn thêm một trong ba dấu \(\{+,-, * \}\) vào giữa các phần tử của tập hợp.
• Có \(n-1\) khoảng giữa các phần tử mà bạn có thể chèn dấu vào.

Ví dụ, với \(a=[3,4,5]\) bạn có thể thêm vào các dấu biến nó trở thành biểu thứ \(3+4-5\). Giá trị của biểu thức này là \(2\).

Hãy liệt kê hết các cách chèn dấu mà giá trị của biểu thức được tạo ra là \(m\).

Input

• Dòng thứ nhất chứa hai số nguyên \(n\), \(m\) \((1 \leq n < 10, |m| \leq 10^{18})\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(|A_i| \leq 10^9\))

Output

• In ra nhiều dòng, mỗi dòng là một biểu thức hợp lệ. Các biểu thức in tăng dần theo thứ tự từ điển. Xem ví dụ để in đáp án được chính xác.

Example

5 0
4 1 2 3 10 

4*1+2*3-10
4+1*2*3-10
4+1+2+3-10

5 42
10 5 4 6 2 

10*5+4-6*2
10*5-4-6+2
10+5*4+6*2