สมมติว่ามีรูปหลายเหลี่ยมปกติ n ด้าน แทนด้วย binary string ความยาว n จุดยอดสีฟ้า (0) หรือแดง (1) ตามเข็มนาฬิกา ต้องนับสามเหลี่ยมสมานฐานที่จุดยอดเป็นจุดยอดของรูปหลายเหลี่ยม และสีเหมือนกันทั้งสามจุด
ตัวอย่าง polygon = "111010" ผลลัพธ์ = 2 (สามเหลี่ยม ACE และ AFE)
ขั้นตอนการแก้ปัญหา
- all(n): จำนวนสามเหลี่ยมสมานฐานทั้งหมดใน n-gon (ไม่สนสี)
- non(a, n): จำนวนสามเหลี่ยมสมานฐานที่สีไม่เหมือนกันทั้งสามจุด
- คำตอบ = all(n) - non(a,n)/2
- แยกกรณี n คี่ และ 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[int((i+n1)%n)]: s -= 2
if a[i] != a[int((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
s += s10 * s11 * 8
s += s00 * s11 * 4
s += s10 * s01 * 4
n1 = n/2
i = 0
while i < n:
if a[i] != a[int((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[int((i+n1)%n)]: s -= 2
if a[i] != a[int((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))
อินพุต
111010
เอาต์พุต
2
