Tóm tắt đề bài

Cho số tự nhiên \(N\) (\(N \le 10^9\)). Hãy tìm số tự nhiên nhỏ nhất \(K\) sao cho:

• Tổng các số lẻ trong đoạn \([1, K]\) lớn hơn
• Tổng các số chẵn trong đoạn \([K+1, N]\)

In ra \(K\) nhỏ nhất thỏa mãn.

Phân tích

Gọi:

• \(S_{\text{lẻ}}(K)\) = tổng các số lẻ từ \(1\) đến \(K\)
• \(S_{\text{chẵn}}(K)\) = tổng các số chẵn từ \(K+1\) đến \(N\)

Ta cần tìm \(K\) nhỏ nhất sao cho \(S_{\text{lẻ}}(K) > S_{\text{chẵn}}(K)\).

Công thức tính nhanh

1) Tổng các số lẻ từ \(1\) đến \(K\)

Số lượng số lẻ \(\le K\) là \(x = \left\lceil \frac{K}{2} \right\rceil = \frac{K+1}{2}\) (lấy phần nguyên).

Tổng \(x\) số lẻ đầu tiên bằng \(x^2\), nên:

2) Tổng các số chẵn từ \(K+1\) đến \(N\)

Ta tìm số chẵn đầu tiên \(\ge K+1\) và số chẵn cuối cùng \(\le N\):

• \(L = K+1\), nếu \(L\) lẻ thì \(L := L+1\)
• \(R = N\), nếu \(R\) lẻ thì \(R := R-1\)

Nếu \(L>R\) thì không có số chẵn, tổng bằng \(0\).

Ngược lại, dãy chẵn là cấp số cộng công sai \(2\), số phần tử:

Tổng:

Tính đơn điệu để dùng tìm kiếm nhị phân

Khi tăng \(K\):

• \(S_{\text{lẻ}}(K)\) không giảm (thường tăng)
• \(S_{\text{chẵn}}(K)\) không tăng (vì đoạn \([K+1, N]\) bị thu hẹp)

Do đó biểu thức \(S_{\text{lẻ}}(K) > S_{\text{chẵn}}(K)\) sẽ chuyển từ sai sang đúng tại một ngưỡng, nên ta có thể dùng binary search để tìm \(K\) nhỏ nhất thỏa.

Hướng giải quyết

Ý tưởng

• Nhị phân trên \(K\) trong đoạn \([1, N]\)
• Với mỗi \(K\), tính \(S_{\text{lẻ}}(K)\) và \(S_{\text{chẵn}}(K)\) bằng công thức \(O(1)\)
• Nếu \(S_{\text{lẻ}}(K) > S_{\text{chẵn}}(K)\):
  • \(K\) có thể là đáp án, thử tìm nhỏ hơn: dịch phải \(phai = K-1\)
• Ngược lại:
  • Cần tăng \(K\): dịch trái \(trai = K+1\)

Các bước theo code đã AC

1. Khởi tạo trai = 1, phai = N, kq = N
2. Lặp khi trai <= phai:
   1. K = (trai + phai)//2
   2. Tính:
      • x = (K+1)//2, tong_le = x*x
      • Tính tong_chan bằng cách chỉnh L, R về chẵn rồi dùng công thức cấp số cộng
   3. So sánh:
      • Nếu tong_le > tong_chan: cập nhật kq = K, phai = K-1
      • Ngược lại: trai = K+1
3. In kq

Lưu ý / Pitfall

• Phải xử lý đúng trường hợp không có số chẵn trong \([K+1, N]\) (khi \(L>R\)).
• Với \(N\) lớn tới \(10^9\), tổng có thể lớn cỡ \(10^{18}\), nhưng Python dùng số nguyên lớn nên an toàn.

Độ phức tạp

• Thời gian: \(O(\log N)\) do tìm kiếm nhị phân
• Bộ nhớ: \(O(1)\)

Code tham khảo

N = int(input())
trai = 1
phai = N
kq = N

while trai <= phai:
    K = (trai + phai) // 2

    # Tổng các số lẻ từ 1 đến K
    x = (K + 1) // 2          # số lượng số lẻ <= K
    tong_le = x * x           # 1 + 3 + ... (x số) = x^2

    # Tổng các số chẵn từ K+1 đến N
    L = K + 1
    R = N

    if L % 2 == 1:
        L += 1
    if R % 2 == 1:
        R -= 1

    if L > R:
        tong_chan = 0
    else:
        dem = (R - L) // 2 + 1
        tong_chan = (L + R) * dem // 2

    # Binary search theo điều kiện
    if tong_le > tong_chan:
        kq = K
        phai = K - 1
    else:
        trai = K + 1

print(kq)