Hint bài toán
Giao lưu contest
Bước 1: Tổng lớn nhất
Chọn 2 số lớn nhất là n và n - 1.
Python
M = 2 * n - 1
Ví dụ n = 50:
M = 2*50 - 1 = 99
Bước 2: Tìm số dạng 10^k
Ta cần tìm p = 10^k lớn nhất sao cho:
p <= M
Code:
Python
p = 1
while p * 10 <= M:
p = p * 10
Ví dụ:
M = 299
p = 100
Khi đó tổng tốt nhất sẽ kết thúc bằng:
p - 1 = 99
Bước 3: Các tổng cần xét
Nếu p = 100, các tổng tốt nhất là:
99, 199, 299, 399, ...
Công thức:
S = p - 1
S = S + p
Code:
Python
S = p - 1
while S <= M:
# đếm cặp có tổng S
S = S + p
Bước 4: Đếm số cặp có tổng S
Ta cần:
a + b = S
1 <= a < b <= n
Vì:
b = S - a
Điều kiện b <= n:
S - a <= n
=> a >= S - n
Vậy a nhỏ nhất:
Python
L = max(1, S - n)
Điều kiện a < b:
a < S - a
2a < S
a <= (S - 1) // 2
Vậy a lớn nhất:
Python
R = (S - 1) // 2
Số cặp:
Python
if L <= R:
ans = ans + R - L + 1
Code gợi ý gần hoàn chỉnh
Python
T = int(input())
for i in range(T):
n = int(input())
if n < 2:
print(0)
continue
M = 2 * n - 1
p = 1
while p * 10 <= M:
p = p * 10
if p == 1:
print(n * (n - 1) // 2)
continue
ans = 0
S = p - 1
while S <= M:
L = max(1, S - n)
R = (S - 1) // 2
if L <= R:
ans = ans + R - L + 1
S = S + p
print(ans)
Câu nhớ nhanh:
M = 2n - 1
p = 10^k lớn nhất <= M
Tổng tốt nhất: p-1, 2p-1, 3p-1, ...
Đếm a từ L đến R
Bình luận