선 위에 m개의 색상을 가진 n개의 서로 다른 점이 있으며, m ≤ n입니다. S를 이 점들의 집합이라 합시다. 다음을 만족하는 공집합이 아닌 부분집합 C ⊆ S를 선택하려고 합니다.

S - C에 속하지 않는 모든 점 p에 대해, C에 있는 점들 중 p에 가장 가까운 점은 p와 같은 색을 갖습니다. 물론, C에 p에 가장 가까운 점이 두 개 이상 있다면, 그중 하나가 p와 같은 색을 갖는 것으로 충분합니다.

예를 들어, 그림 G.1에는 두 가지 색상으로 1부터 6까지 레이블이 지정된 여섯 개의 점이 있습니다. 점 4와 5는 빨간색이고 나머지는 파란색입니다. 집합 {2, 4, 6}은 위의 성질을 만족합니다. 그러나 집합 {2, 4}는 이 성질을 만족하지 않습니다. {2, 4}에서 점 6에 가장 가까운 점은 점 4이고, 이는 점 6의 색상과 다르기 때문입니다. 실제로 집합 {2, 4, 6}은 이 성질을 만족하는 최소 기수 부분 집합입니다.

선 위에 서로 다른 n개의 점과 m개의 점이 주어졌을 때, 위 속성을 만족하는 최소 기수를 갖는 S의 비어 있지 않은 부분 집합 C를 찾고 최소 기수를 출력하는 프로그램을 작성하세요.

#4390 upload 13 done 3 how_to_reg 2

Same Color timer 1s memory 512MB

#4390

Same Color 1s 512MB