Redistricting timer 2초 memory 512MB

Bovinopolis 대도시는 항상 두 주요 젖소 품종(홀스타인과 건지)이 정치적으로 경쟁하고 있다. 두 품종 모두 Bovinopolis 정부에서 충분한 영향력을 유지하고 싶어한다.

Bovinopolis의 대도시 지역은 N개의 목초지로 이루어진 일직선 형태이며, 각각의 목초지에는 한 마리의 젖소가 있다. 젖소는 홀스타인(H) 또는 건지(G) 둘 중 하나이다.

Bovinopolis 정부는 이 목초지를 여러 개의 연속된 구획으로 나누려고 한다. 각 구획은 최대 K개의 목초지를 포함할 수 있으며, 모든 목초지는 정확히 하나의 구획에 포함되어야 한다. 현재 정부는 홀스타인들이 장악하고 있기 때문에, 건지 우세 지역 또는 동점 지역이 최소화되는 방식으로 구획을 나누고 싶어한다.

• 구획에서 건지의 수가 홀스타인보다 많으면 그 구획은 건지 우세 지역이다.

• 구획에서 건지와 홀스타인의 수가 같다면 그 구획은 동점 지역이다.

이에 맞서, 건지 젖소들의 연합은 최악의 시나리오에서 건지 우세 지역 또는 동점 지역의 최소 개수가 얼마인지 알고 싶어한다. 이를 구하라.