Học sinh giỏi 9 Quảng Ngãi 2025-2026

Cho số nguyên dương \(N\) (\(0 < N \le 2 \cdot 10^9\)).

Yêu cầu

• Tính tổng bình phương các chữ số của \(N\).

Input

• Một số nguyên dương \(N\).

Output

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

Example

12

5

Tý muốn cắt một sợi dây có chiều dài \(N\) (mét) thành 3 đoạn dây có chiêu dài mỗi đoạn là số nguyên dương (đơn vị mét) sao cho 3 đoạn dây này là 3 cạnh của một tam gịác cân có cạnh đáy lớn hơn cạnh bên.

Lưu ý: Tam giác cân là tam giác có hai cạnh bằng nhau, hai cạnh bằng nhau gọi là hai cạnh bên, cạnh còn lại gọi là cạnh đáy.

Yêu cầu: Em hãy giúp Tý tính có bao nhiêu cách cắt đoạn dây này.

Dữ liệu

• Một số nguyên dương \(N\) (\(N< 10^{16}\))

Kết quả

• Ghi ra số \(M\) là số cách cắt sợi dây theo yêu cầu.

Input

19

Output

2

Giải thích: Có 2 cách cắt sợi dây thành 3 đoạn thỏa mãn đề là: (\(5m; 5m; 9m\)) và (\(6m; 6m; 7m\)).

Lưu ý:: Các cách cắt sợi dây thành 3 đoạn (\(x\) mét; \(x\) mét; \(y\) mét) và các hoán vị của bộ 3 số . (\(x;x;y\)) chì được tính là 1 cách cắt. Chẳng hạn: Cách cắt thành các đoạn (\(5m; 5m; 9m\)) và các hoán vị của nó là (\(5m; 9m; 5m\)) hoặc (\(9m; 5m; 5m\)) chỉ được tính là 1 cách cắt.

Giới hạn

• Có 20% test ứng với \(N \le 10^2\);
• Có 30% test ứng với \(10^2 < N \le 10^6\);
• Có 30% test ứng với \(10^6 < N \le 10^9\);
• Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Nguồn: THTB - Cấp TP 2021.

Trong chuyến thám hiểm đến hành tinh Golden, nhóm bạn Nô-bi-ta vô tình khám phá một căn hầm bí mật, họ buộc phải nhập mật mã mới mở được cánh cửa. Trên cửa có khắc một đoạn mật mã \(S\) chỉ gồm hai loại ký tự là A và B. Nô-bi-ta phát hiện thấy một phiến đá viết hướng dẫn cách duy nhất để mở cánh cửa, đó là phải tìm được độ dài của đoạn chữ cân bằng hoàn hảo dài nhất của \(S\). Một đoạn chữ liên tiếp được đánh giá là cân bằng hoàn hảo nếu số lượng ký tự A trong đoạn đó bằng chính xác số lượng ký tự B. Do đoạn mật mã rất dài nên các bạn giúp đỡ nhóm Nô-bi-ta hoàn thành nhiệm vụ trên.

Yêu cầu

Hãy tìm và in ra độ dài của đoạn chữ cân bằng hoàn hảo dài nhất trong đoạn mật mã \(S\).

Input

• Một xâu \(S\) duy nhất (chỉ gồm hai loại ký tự A và B).

Output

• Ghi ra một số nguyên duy nhất là độ dài của đoạn chữ cân bằng hoàn hảo dài nhất tìm được. In ra \(0\) nếu \(S\) không có đoạn cân bằng hoàn hảo.

Constraints

• Độ dài của xâu \(S\) không vượt quá \(10^6\).

Example

AABABB

6

AAB

2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Độ dài xâu \(S \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Độ dài xâu \(S \le 10^6\).

Trong tựa game chiến thuật "Đế Chế Cổ Đại", bạn đóng vai một vị tướng quân đang thiết lập một tuyến phòng thủ dọc theo biên giới. Trên tuyến đường biên giới thẳng tắp này, có sẵn \(N\) vị trí bằng phẳng khác nhau có thể dùng để xây dựng thành lũy. Tuy nhiên, tài nguyên hiện tại chỉ đủ để bạn xây dựng đúng \(K\) thành lũy (\(K < N\)), mỗi thành lũy được xây trên một vị trí. Giá trị khoảng cách giữa hai thành lũy gần nhau tương ứng với mức chênh lệch giá trị của hai vị trí đó.

Kẻ thù trong game sở hữu những cỗ máy bắn đá có khả năng sát thương diện rộng. Để giảm thiểu thiệt hại, tránh việc một lần bắn mà đá đập trúng nhiều thành lũy cùng lúc, bạn cần phải bố trí \(K\) thành lũy này sao cho khoảng cách gần nhất giữa hai thành lũy bất kỳ cần phải càng xa càng tốt.

Yêu cầu: Cho \(N\) vị trí trên bản đồ và \(K\) vị trí để xây thành lũy. Tìm giá trị \(X\) sao cho \(X\) là lớn nhất trong số các khoảng cách gần nhau nhất giữa hai thành lũy bất kỳ.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) (\(2 \leq K < N\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(0 \leq A_i \leq 10^9\)) là các vị trí cần xây dựng. Các vị trí này chưa sắp xếp.

Output

• Ghi ra giá trị của \(X\).

Example

5 3
1 2 8 4 9

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \leq 10^5\).