벌집 채우기

아래와 같이 벌집 모양의 육각형 판이 있다.

먼저, 당신이 육각형 판에서 몇 개의 칸을 색칠해야 한다.

다음으로, “시뮬레이션 시작하기” 버튼을 누르면, 컴퓨터는 다음과 같은 과정을 계속해서 수행할 것이다.

• 각각의 칸에 대해, “인접한 여섯 개의 칸들 중 세 개 이상이 색칠되어 있으면, 자신을 색칠한다” 를 시행한다.

당신이 색칠한 육각형 판에서 시작해서, 위 과정을 충분히 반복해서 수행한 뒤에는, 육각형 판에 있는 모든 칸을 색칠하는 데 성공해야 한다. 그리고 시뮬레이션을 시작하기 전 당신이 직접 색칠한 칸의 개수를 최소화해야 한다. 어떻게 해야 하는가?

모든 칸을 색칠하는 데 성공한 뒤 제출 버튼을 누르면, 다음과 같은 방법으로 계산된 점수를 받는다.

시뮬레이션을 시작하기 전 색칠한 칸의 개수를 , 의 가능한 최솟값을 이라고 하자.

• 이라면, 전체 점수의 100%를 받는다.
• 이라면, 전체 점수의 1/2을 받는다.
• 이라면, 전체 점수의 1/5를 받는다.
• 이라면, 전체 점수의 0%를 받는다.

제출하지 않으면 득점할 수 없음에 유의하라.

문제 형식

인터랙티브

출처

• KOI 2023 1차대회 고등부 1교시 17번
• KOI 2023 1차대회 중등부 1교시 18번
• KOI 2023 1차대회 초등부 1교시 20번