Tóm tắt đề bài

Cho \(N\) (số chẵn) và dãy: \(1, N, 2, N-1, 3, N-2, \ldots\) (xen kẽ số nhỏ tăng dần và số lớn giảm dần). Nhập \(N, M\) \((1 \le M \le N \le 10^9)\), hãy tính tổng \(M\) số đầu tiên của dãy.

Phân tích

• Dãy được ghép theo cặp:

  • Cặp thứ \(k\) (bắt đầu từ \(k=1\)) là: \(k\) và \(N-(k-1)\).

  • Tổng mỗi cặp:

    \(k + (N-(k-1)) = N+1\)

• Vì vậy:

  • Mỗi 2 phần tử liên tiếp trong dãy luôn có tổng bằng \(N+1\).
  • Ta chỉ cần đếm có bao nhiêu cặp đầy đủ trong \(M\) phần tử đầu và xử lý thêm 1 phần tử lẻ (nếu \(M\) lẻ).
• Ràng buộc \(N, M\) lớn tới \(10^9\) nên cần lời giải \(O(1)\), không thể sinh dãy.

Hướng giải quyết

Nhận xét

• Gọi \(t = \left\lfloor \frac{M}{2} \right\rfloor\) là số cặp đầy đủ trong \(M\) phần tử đầu.
  • Tổng của \(2t\) phần tử đầu là \(t \cdot (N+1)\).
• Nếu \(M\) lẻ, còn dư thêm phần tử thứ \(2t+1\):
  • Các vị trí lẻ là \(1, 2, 3, \ldots\) nên phần tử thứ \(2t+1\) chính là \(t+1\).
  • Cộng thêm \((t+1)\).

Thuật toán

1. Đọc \(n, m\).
2. Tính \(t = m // 2\).

3. Khởi tạo:

   \[S = (n+1)\cdot t\]

4. Nếu \(m\) lẻ, cộng thêm \(t+1\).

5. In \(S\).

Liên hệ với code AC đã cho

• Dòng S = (1 + n) * (m // 2) chính là \((n+1)\cdot \left\lfloor \frac{m}{2}\right\rfloor\).
• Nếu m % 2 == 1 thì S += m // 2 + 1 tức là cộng thêm \(t+1\).

Độ phức tạp

• Thời gian: \(O(1)\)
• Bộ nhớ: \(O(1)\)

Code tham khảo

n = int(input())
m = int(input())

# t = số cặp đầy đủ trong m phần tử đầu
t = m // 2

# Mỗi cặp có tổng n + 1
S = (n + 1) * t

# Nếu m lẻ, còn dư phần tử (t + 1) ở vị trí lẻ tiếp theo
if m % 2 == 1:
    S += t + 1

print(S)