#1037 · Bắt tay

Ví dụ với n=5:

• Người thứ nhất bắt tay với 4 người còn lại -> 4 cái bắt tay.
• Người thứ hai bắt tay với 3 người còn lại (đã tính cái bắt tay với người thứ nhất) -> 3 cái bắt tay.
• Người thứ ba bắt tay với 2 người còn lại (đã tính cái bắt tay với người thứ hai và thứ ba) -> 2 cái bắt tay.
• Người thứ tư bắt tay với 1 người còn lại (đã tính cái bắt tay với người thứ hai, thứ ba và thứ tư) -> 1 cái bắt tay.
• Người thứ năm đã bắt tay với 4 người còn lại (tính ở trên)

=> Vậy có tất cả: 4 + 3 + 2 + 1 = 10 cái bắt tay.

Từ kết quả trên ta thấy đó là một cấp số cộng, công thức tính cấp số cộng của kết quả trên là: s = n(n+1)/2

Ta để ý thấy n = 5 nhưng kết quả chính xác là cấp số cộng chỉ cộng đến 4, tức là cộng đến n-1.

Thay n-1 vào công thức s ta được kết quả S = n(n-1)/2

Ta có p1 p2 p3 thì

p1 bắt tay p2

p1 bắt tay p3

p2 bắt tay p3

=> Các cặp thoả mãn là (p1, p2), (p1, p3), (p2, p3)

=> Tổng các cặp thoả mãn là 3 (TTM)

Tạo công thức tính nhanh thông qua ma trận TTM nhân TTM <=> 3 nhân 3

    p1 p2 p3
p1  X  T  T
p2  X  X  T
p3  X  X  X

Trong đó:
T là thoả mãn
X là không thoả mãn

Ta thấy rằng các cặp thoả mãn là nửa tam giác trên đường chéo chính.

Đầu tiên ta n*n để tính tổng ma trận này.

Ở dòng cuối p3 thì cả dòng toàn X thế nên loại bỏ đi n*(n-1)

Ma trận còn:

    p1 p2 p3
p1  X  T  T
p2  X  X  T

Nhận ra ngay tổng các cặp thoả mãn = không thoả mãn => Chia 2

=> (n*(n-1))/2 vậy đã xong bài toán bắt tay này nhé :vv

Tổng độ phức tạp o(1)

temp = int(input()) arr = [] for i in range(temp):

n = int(input())
arr.append(n)

for k in arr:

print(k*(k-1)//2)