Phân tích đề:

Các viên gạch được đánh số theo dạng tam giác đều (kim tự tháp):

• Hàng 1 có 1 viên: 1

• Hàng 2 có 2 viên: 2 3

• Hàng 3 có 3 viên: 4 5 6

• Hàng 4 có 4 viên: 7 8 9 10

• ...

• Hàng n có n viên

Khi rút một viên gạch, các viên ở phía trên mà có "chân" đặt lên viên đó sẽ bị ảnh hưởng.

Yêu cầu:

Với mỗi viên gạch có số hiệu a_i, tính tổng số hiệu của tất cả các viên gạch bị ảnh hưởng khi rút viên a_i ra.

Cách giải bài toán: Bước 1: Tìm vị trí của viên gạch

Viên gạch có số hiệu a nằm ở hàng thứ r và cột thứ c.
Ta có thể tính r bằng cách tìm số hàng sao cho tổng viên từ hàng 1 đến hàng r vừa lớn hơn hoặc bằng a:

Tổng soˆˊ vieˆn gạch đeˆˊn haˋng r=r(r+1)2\text{Tổng số viên gạch đến hàng } r = \frac{r(r+1)}{2}Tổng soˆˊ vieˆn gạch đeˆˊn haˋng r=2r(r+1)​

=> Dùng nhị phân để tìm r.

Sau đó, tính c (cột thứ mấy trong hàng r) bằng:

c=a−(r−1)r2c = a - \frac{(r-1)r}{2}c=a−2(r−1)r​ Bước 2: Duyệt ngược lên trên

Bắt đầu từ viên a, đi ngược lên từng hàng, kiểm tra 2 viên gạch nằm chồng trên nó (nếu có) là:

• Cột c

• Cột c-1

Cộng tổng số hiệu lại cho đến khi không còn viên nào phía trên.

Code mẫu (Python):

pythonSao chépChỉnh sửadef find_position(a):
    # Tìm hàng r mà viên a nằm
    low, high = 1, 2 * 10**9
    while low < high:
        mid = (low + high) // 2
        if mid * (mid + 1) // 2 >= a:
            high = mid
        else:
            low = mid + 1
    r = low
    # Tính cột (1-based)
    base = (r - 1) * r // 2
    c = a - base
    return r, c

def sum_impacted(a):
    r, c = find_position(a)
    total = 0
    while r >= 1 and 1 <= c <= r:
        base = (r - 1) * r // 2
        total += base + c
        r -= 1
        if c > 1:
            c -= 1
    return total

Q = int(input())
for _ in range(Q):
    a = int(input())
    print(sum_impacted(a))

Ví dụ chạy:

Với input:

Sao chépChỉnh sửa5
5
6
14
26
22

Output sẽ là:

Sao chépChỉnh sửa11
10
50
155
63