Chương trình Python đếm tam giác cân cùng màu từ đỉnh đa giác đều tô màu

Cho đa giác đều n cạnh, đỉnh được tô màu xanh (0) hoặc đỏ (1) theo chiều kim đồng hồ (chuỗi nhị phân). Đếm số tam giác cân có 3 đỉnh cùng màu.

Ví dụ: "111010" → 2 tam giác (ACE và AFE).

Giải pháp toán học

• Tổng số tam giác cân trong đa giác đều n cạnh: hàm all(n).
• Số tam giác cân không cùng màu: hàm non(colors, n).
• Kết quả = all(n) - non(colors, n)/2.
• Xét riêng trường hợp n chẵn/lẻ, n chia hết 3 (tam giác đều).

Ví dụ mã nguồn

def all(n):
    if n % 2 == 1:
        no = n*(n-1)/2
    else:
        no = n*(n/2-1)
    if n % 3 == 0:
        no -= n/3*2
    return no

def non(a, n):
    if n % 2 == 1:
        s0 = s1 = 0
        i = 0
        while i < n:
            if a[i] == '0': s0 += 1
            else: s1 += 1
            i += 1
        s = s0*s1*6
        if n % 3 == 0:
            n1 = n//3; n2 = n1*2
            i = 0
            while i < n:
                if a[i] != a[(i+n1)%n]: s -= 2
                if a[i] != a[(i+n2)%n]: s -= 2
                i += 1
    else:
        s00 = s01 = s10 = s11 = s = 0
        i = 0
        while i < n:
            if a[i] == '0': s00 += 1
            else: s01 += 1
            i += 2
        i = 1
        while i < n:
            if a[i] == '0': s10 += 1
            else: s11 += 1
            i += 2
        s += s00*s01*8 + s10*s11*8 + s00*s11*4 + s10*s01*4
        n1 = n//2
        i = 0
        while i < n:
            if a[i] != a[(i+n1)%n]: s -= 2
            i += 1
        if n % 3 == 0:
            n1 = n//3; n2 = n1*2
            i = 0
            while i < n:
                if a[i] != a[(i+n1)%n]: s -= 2
                if a[i] != a[(i+n2)%n]: s -= 2
                i += 1
    return s/2

def solve(polygon):
    n = len(polygon)
    no = all(n) - non(polygon, n)/2
    return int(no)

polygon = "111010"
print(solve(polygon))  # 2

Đầu vào / Đầu ra

Input:  111010
Output: 2