Tóm tắt đề bài

Cho một bảng vuông kích thước \(N \times N\) chứa các số từ \(1\) đến \(N^2\) được điền theo quy tắc ziczac:

• Hàng lẻ (\(1, 3, 5, \dots\)): Điền từ trái sang phải.
• Hàng chẵn (\(2, 4, 6, \dots\)): Điền từ phải sang trái.
• Ô \((1, 1)\) bắt đầu bằng số \(1\).

Yêu cầu: Tính tổng các số nằm trên cột thứ \(X\) của bảng.

Phân tích

Để giải bài toán này, ta cần xác định giá trị của ô nằm ở hàng \(i\) và cột \(X\), ký hiệu là \(A[i][X]\).

Xét hàng thứ \(i\):

• Các số ở hàng \(i\) sẽ nằm trong phạm vi từ \((i-1) \times N + 1\) đến \(i \times N\).
• Trường hợp \(i\) là số lẻ:
  • Hàng được điền từ trái sang phải.
  • Cột 1 là \((i-1) \times N + 1\), cột 2 là \((i-1) \times N + 2, \dots\)
  • Công thức tổng quát cho cột \(X\): \(A[i][X] = (i-1) \times N + X\).
• Trường hợp \(i\) là số chẵn:
  • Hàng được điền từ phải sang trái.
  • Cột \(N\) là \((i-1) \times N + 1\), cột \(N-1\) là \((i-1) \times N + 2, \dots\)
  • Công thức tổng quát cho cột \(X\):
    • Ta nhận thấy giá trị tại cột \(X\) và giá trị tại cột \(1\) đối xứng nhau qua tâm hàng.
    • Giá trị đầu hàng (cột \(N\)) là \((i-1) \times N + 1\).
    • Giá trị cuối hàng (cột \(1\)) là \(i \times N\).
    • Công thức: \(A[i][X] = i \times N - X + 1\).

Ví dụ với \(N=6, X=3\):

• Hàng 1 (lẻ): \(A[1][3] = (1-1) \times 6 + 3 = 3\).
• Hàng 2 (chẵn): \(A[2][3] = 2 \times 6 - 3 + 1 = 10\).
• Hàng 3 (lẻ): \(A[3][3] = (3-1) \times 6 + 3 = 15\).
• Hàng 4 (chẵn): \(A[4][3] = 4 \times 6 - 3 + 1 = 22\).
• ...

Hướng giải quyết

1. Duyệt vòng lặp từ \(i = 1\) đến \(N\) để đi qua từng hàng.
2. Với mỗi hàng \(i\), kiểm tra tính chẵn lẻ của \(i\):
   • Nếu \(i\) lẻ: Cộng vào tổng giá trị \((i-1) \times N + X\).
   • Nếu \(i\) chẵn: Cộng vào tổng giá trị \(i \times N - X + 1\).
3. In ra tổng cuối cùng.

Lưu ý về tối ưu:
Với \(N \le 10^5\), độ phức tạp \(O(N)\) là hoàn toàn đủ để vượt qua bài toán trong giới hạn thời gian. Tuy nhiên, ta có thể tính toán bằng công thức toán học \(O(1)\) dựa trên cấp số cộng nếu cần thiết, nhưng với bài này \(O(N)\) đã là tối ưu cho Subtask 2.

Độ phức tạp

• Thời gian: \(O(N)\) do duyệt qua \(N\) hàng.
• Bộ nhớ: \(O(1)\) chỉ sử dụng các biến đơn lẻ để lưu trữ.

Code tham khảo

# Đọc dữ liệu đầu vào
N = int(input())
X = int(input())

tong = 0
# Duyệt qua từng hàng từ 1 đến N
for i in range(1, N + 1):
    if i % 2 == 1:
        # Hàng lẻ: điền từ trái sang phải
        # Công thức: (số hàng trước đó * N) + vị trí cột
        tong += (i - 1) * N + X
    else:
        # Hàng chẵn: điền từ phải sang trái
        # Công thức: (số hàng hiện tại * N) - vị trí cột + 1
        tong += i * N - X + 1

# In kết quả cuối cùng
print(tong)