2025 THT bảng B - Buổi 17

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.

Một vòng tròn chứa \(2n\) vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ \(1\) đến \(2n\) theo chiều kim đồng hồ. Cần điền các số tự nhiên từ \(1\) đến \(2n\) mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ \(1\) luôn là số \(1\).

Dữ liệu:

• Một dòng chứa số nguyên dương \(n (1 < n < 10)\)

Kết quả:

• Một dòng ghi số lượng các cách điền số tìm được (\(k\)).

Sample Input

3

Sample Output

2

Sample Input

4

Sample Output

4

Giải thích:

• Ví dụ 1:

\({1, 4, 3, 2, 5, 6}\)

\({1, 6, 5, 2, 3, 4}\)

• Ví dụ 2:

\({1, 2, 3, 8, 5, 6, 7, 4}\)

\({1, 2, 5, 8, 3, 4, 7, 6}\)

\({1, 4, 7, 6, 5, 8, 3, 2}\)

\({1, 6, 7, 4, 3, 8, 5, 2}\)