Tóm tắt đề bài

Cho một số nguyên dương \(N\). Một dãy số "con lắc" được tạo ra theo quy luật thay đổi khoảng giá trị:

• Bước 1: Dãy từ \(1\) đến \(N\).
• Bước 2: Dãy từ \(N-1\) về \(2\).
• Bước 3: Dãy từ \(3\) đến \(N-2\).
• Bước 4: Dãy từ \(N-3\) về \(4\).
  ...
  Quá trình dừng lại khi không thể tạo thêm dãy mới (tức là giới hạn dưới vượt quá giới hạn trên).
  Yêu cầu: Tính tổng tất cả các phần tử trong dãy con lắc này và lấy phần dư cho \(100\).

Phân tích

Xét các bước tạo dãy dưới dạng các khoảng \([L_i, R_i]\):

• Bước 1: \([1, N]\)
• Bước 2: \([2, N-1]\)
• Bước 3: \([3, N-2]\)
• Bước 4: \([4, N-3]\)
• ...
• Bước \(k\): \([k, N-k+1]\)

Quy luật này tiếp diễn cho đến khi \(L_k > R_k\), tức là \(k > N-k+1 \Leftrightarrow 2k > N+1\).
Số lượng bước thực hiện sẽ là \(M = \lceil \frac{N}{2} \rceil\).

Tổng của một dãy từ \(L\) đến \(R\) (không quan trọng chiều tăng hay giảm) luôn là:

Áp dụng vào bước \(k\):

• Độ dài dãy: \(R_k - L_k + 1 = (N - k + 1) - k + 1 = N - 2k + 2\).
• Tổng hai đầu mút: \(L_k + R_k = k + (N - k + 1) = N + 1\).
• Tổng các phần tử bước \(k\): \(S_k = \frac{(N - 2k + 2)(N + 1)}{2}\).

Hướng giải quyết

Công thức toán học

Tổng toàn bộ dãy số \(T\) là tổng của các \(S_k\) với \(k\) chạy từ \(1\) đến \(M\):

Đặt \(A = \sum_{k=1}^{M} (N - 2k + 2)\). Đây là tổng của một cấp số cộng với:

• Số hạng đầu (\(k=1\)): \(a_1 = N\).
• Số hạng cuối (\(k=M\)): \(a_M = N - 2M + 2\).
• Số lượng số hạng: \(M\).
• Công thức tổng: \(A = \frac{M(a_1 + a_M)}{2}\).

Các trường hợp của \(N\)

1. Nếu \(N\) là số chẵn (\(N = 2m\)):

   • \(M = N/2\).
   • \(a_M = N - 2(N/2) + 2 = 2\).
   • \(A = \frac{(N/2)(N + 2)}{2} = \frac{N(N+2)}{4}\).
   • \(T = \frac{N+1}{2} \cdot \frac{N(N+2)}{4} = \frac{N(N+1)(N+2)}{8}\).

2. Nếu \(N\) là số lẻ (\(N = 2m+1\)):

   • \(M = (N+1)/2\).
   • \(a_M = N - 2(\frac{N+1}{2}) + 2 = 1\).
   • \(A = \frac{(\frac{N+1}{2})(N + 1)}{2} = \frac{(N+1)^2}{4}\).
   • \(T = \frac{N+1}{2} \cdot \frac{(N+1)^2}{4} = \frac{(N+1)^3}{8}\).

Vì \(N \le 10^8\), ta có thể tính trực tiếp công thức này và lấy mod 100. Lưu ý sử dụng kiểu dữ liệu số nguyên lớn hoặc thực hiện phép chia trước khi lấy dư.

Độ phức tạp

• Thời gian: \(O(1)\) do chỉ sử dụng công thức toán học.
• Bộ nhớ: \(O(1)\).

Code tham khảo

def solve():
    try:
        line = input().split()
        if not line:
            return
        n = int(line[0])
    except EOFError:
        return

    # Tính tổng theo công thức rút gọn
    # Nếu N chẵn: T = N * (N + 1) * (N + 2) / 8
    # Nếu N lẻ: T = (N + 1)^3 / 8

    if n % 2 == 0:
        # N chẵn
        # Tích ba số liên tiếp n*(n+1)*(n+2) luôn chia hết cho 8 khi n chẵn
        ans = (n * (n + 1) * (n + 2)) // 8
    else:
        # N lẻ
        # (n+1) là số chẵn nên (n+1)^3 chia hết cho 8
        ans = ((n + 1) ** 3) // 8

    # Kết quả là tổng mod 100
    print(ans % 100)

if __name__ == "__main__":
    solve()

Giải thích thêm về Code AC của bạn:
Code của bạn sử dụng cách tính tổng cấp số cộng cho từng phần:

• tong_dau: Tổng từ \(1\) đến \(N\).
• so_luong: Số lượng các dãy con (\(M\)).
• tong_cuoi: Tổng của dãy con cuối cùng.
• Sau đó dùng công thức tổng cấp số cộng cho các tổng của từng bước. Cách này tương đương với việc tính \(\sum S_k\) và cho kết quả chính xác.