2025 THT bảng B - Buổi 26

Một số nguyên dương \(N\) được gọi là số đẹp nếu nó thỏa mãn các điều kiện sau:

• Số đó là số chính phương.
• Tổng các chữ số của nó là một số Fibonacci.

Yêu cầu: Cho số nguyên dương \(N\), đếm số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Dữ liệu

Vào từ file văn bản BNUM.INP một số nguyên dương \(N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^9\).

Kết quả

Ghi vào file văn bản BNUM.OUT một số nguyên là số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Ràng buộc

• Subtask 1: \(60\%\) số test ứng với \(1 \le N \le 10^6\)
• Subtask 2: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

50

2

Thầy Minh tổ chức buổi phát thưởng cho các học sinh đạt giải trong kỳ thi học sinh giỏi môn Tin. Thầy có X chiếc bút và Y quyển tập, thầy sẽ phát hết các phần thưởng cho các bạn học sinh và mong muốn số chiếc bút và số quyển tập được chia đều cho các bạn.

Yêu cầu: Cho hai số nguyên \(X\) và \(Y\). Hãy tìm tất cả các cách phát quà thỏa mãn điều kiện của thầy Minh.

Dữ liệu

Vào từ file văn bản GIFTS.INP gồm một dòng chứa \(2\) số nguyên dương \(X, Y\).

Dữ liệu đảm bảo: \(1 \le X, Y \le 10^{14}\).

Kết quả

Ghi vào file văn bản GIFTS.OUT một số nguyên là số cách phát quà thỏa điều kiện đề bài.

Ràng buộc

• Subtask 1: \(60\%\) số test ứng với \(1 \le X, Y \le 10^6\)
• Subtask 2: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

4 6

2

Cho một dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Yêu cầu: Hãy tìm đoạn con \([l, r]\) \((1 \le l \le r \le n)\) gồm các phần tử liên tiếp \(A_l, A_{l+1}, \dots, A_{r-1}, A_r\) của dãy \(A\) sao cho tổng \(A_l + A_{l+1} + \dots + A_{r-1} + A_r\) là lớn nhất

Dữ liệu

Vào từ file văn bản MAXS.INP:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^5\) và \(|A_i|\le 10^9\).

Kết quả

Ghi vào file văn bản MAXS.OUT một số nguyên là tổng lớn nhất tìm được.

Ràng buộc

• Subtask 1: \(20\%\) số test ứng với \(1 \le N \le 100\)
• Subtask 2: \(20\%\) số test ứng với \(1 \le N \le 10^4\)
• Subtask 3: \(20\%\) số test ứng với \(A_i \ge 0\).
• Subtask 4: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

6
2 -3 8 4 -5 3

12

Vườn hoa của nhà Minh nở rộ \(N\) khóm hoa đẹp, khóm hoa thứ \(i\) có \(A_i\) bông hoa. Do nhu cầu của dịp lễ 8/3 lớn nên người lái buôn muốn mua càng nhiều hoa của vườn càng tốt. Tuy nhiên địa hình vườn nhà Minh không thể cắt hoa của \(K\) khóm hoa liên tiếp, vì vậy Minh cần tìm cách cắt hoa sao cho cắt được tổng số bông hoa là nhiều nhất có thể.

Yêu cầu: Hãy xác định số lượng bông hoa nhiều nhất có thể cắt được.

Dữ liệu

Vào từ file văn bản FCUT.INP:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) lần lượt là số bông hoa mỗi khóm hoa.

Dữ liệu đảm bảo: \(2 \le K \le N \le 10^5\) và \(1 \le A_i \le 10^9\).

Kết quả

Ghi vào file văn bản FCUT.OUT một số nguyên là tổng số bông hoa nhiều nhất có thể cắt được.

Ràng buộc

• Subtask 1: \(40\%\) số test ứng với \(K = 3\).
• Subtask 2: \(40\%\) số test ứng với \(2 \le K \le N \le 10^3\).
• Subtask 3: \(20\%\) số test không có ràng buộc gì thêm.

Ví dụ

Giải thích

7 3
2 4 1 5 3 1 6

20

5 2
10 4 7 3 4

21

Cho một bảng hình chữ nhật kích thước \(𝑚 \times 𝑛\) được chia thành lưới ô vuông đơn vị \(𝑚\) hàng, \(𝑛\) cột. Các hàng được
đánh số từ 1 tới \(𝑚\) theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 tới \(𝑛\) theo thứ tự từ trái qua phải.

Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột \(𝑗\) sẽ được tô từ trên xuống dưới: \(ℎ_𝑗\) ô
màu vàng tiếp đến là \(𝑚 - ℎ_𝑗\) ô màu xanh. Như vậy tình trạng màu trên bảng hoàn toàn xác định nếu ta biết được
số hàng \(𝑚\), số cột \(𝑛\) và các số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛\).

Yêu cầu: Hãy xác định một hình chữ nhật gồm các ô trong bảng đã cho thỏa mãn các yêu cầu sau:

• Có cạnh song song với cạnh bảng.
• Đơn sắc (chỉ gồm các ô vàng hoặc chỉ gồm các ô xanh).
• Diện tích lớn nhất có thể.

Input

• Dòng 1: Chứa hai số nguyên dương \(𝑚, 𝑛 (𝑚, 𝑛 \leq 5 \times 10^5)\).
• Dòng 2: Chứa \(𝑛\) số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛 (\forall 𝑗: 0 \leq ℎ_𝑗 \leq 𝑚)\).

Output

• Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật tìm được.

Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách.

Scoring

• Subtask \(1\) (\(9.5\%\) số điểm): \(𝑚, 𝑛 \leq 400\)
• Subtask \(2\) (\(42.9\%\) số điểm): \(𝑚, 𝑛 \leq 10^4\)
• Subtask \(3\) (\(47.6\%\) số điểm): \(𝑚, 𝑛 \leq 10^5\)

Example

5 9
1 3 4 4 5 4 4 3 1 

21