Python의 컬러 정점 정다각형에서 이등변 삼각형의 수를 계산하는 프로그램

<시간/>

크기가 n인 이진 문자열로 표현되는 n개의 변을 가진 하나의 정다각형이 있다고 가정합니다. 정점은 파란색(0) 또는 빨간색(1)으로 채색될 수 있습니다. 시계 방향으로 색칠되어 있습니다. 꼭짓점이 정다각형의 꼭짓점이고 색이 같은 이등변 삼각형의 수를 세어야 합니다.

따라서 입력이 폴리곤 ="111010"과 같으면 출력은 2가 됩니다.

두 개의 삼각형 ACE와 AFE가 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

all() 함수를 정의합니다. n
n mod 2가 1과 같으면 no :=n*(n-1) /2
그렇지 않으면 아니오 :=n*(n/2-1)
n mod 3이 0과 같으면 no :=no - n/3*2
반품 없음
non() 함수를 정의합니다. ,n
n mod 2가 1과 같으면
- s0 :=0, s1 :=0
- i :=0
- 내가
- a[i]가 '0'과 같으면 s0 :=s0 + 1
- 그렇지 않으면 s1 :=s1 + 1
- 나는 :=나는 + 1
s :=s0*s1*6
n mod 3이 0과 같으면
- n1 :=n/3
- n2 :=n1*2
- i :=0
- 내가
- a[i]가 a[(i+n1)mod n]과 같지 않으면
  - s :=s - 2
- a[i]가 a[(i+n2)mod n]과 같지 않으면
  - s :=s - 2
- 나는 :=나는 + 1

그렇지 않으면

s00 :=0, s01 :=0, s10 :=0, s11 :=0, s :=0
i :=0
내가
a[i]가 '0'과 같으면 s00 :=s00 + 1
그렇지 않으면 s01 :=s01 + 1
나는 :=나는 + 2

i :=1

내가

a[i]가 '0'과 같으면 s10 :=s10 + 1

그렇지 않으면 s11 :=s11 + 1

나는 :=나는 + 2

s :=s + s00 * s01 * 8

s :=s + s10 * s11 * 8

s :=s + s00 * s11 * 4

s :=s + s10 * s01 * 4

n1 :=n/2

i :=0

내가

a[i]가 a[(i + n1)mod n]과 같지 않으면

s :=s - 2

나는 :=나는 + 1

n mod 3이 0과 같으면

n1 :=n/3
n2 :=n1*2
i :=0
내가
a[i]가 a[(i+n1)mod n]과 같지 않으면
- s :=s - 2
a[i]가 a[(i+n2)mod n]과 같지 않으면
- s :=s - 2
나는 :=나는 + 1

반환 s/2

메인 방법에서 다음을 수행하십시오. -

n :=다각형의 크기

no :=all(n) - non(polygon, n) /2

반품 없음

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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))

입력

1, 1000