레이팅 미적용농부 존의 \(N\) \((1 \leq N \leq 10^5)\)마리 소들이 한 줄로 배치되어 있다. \(i\)번째 소의 라벨은 \(a_i\)(\(1 \leq a_i \leq N\))이다. 어떤 소들의 그룹이 우정 그룹이 되려면, 그룹의 모든 소가 같은 라벨을 가져야 하고, 각 소가 그룹 내 다른 모든 소로부터 \(x\)칸 이내에 있어야 한다. 여기서 \(x\)는 \([1,N]\) 범위의 정수이다. 모든 소는 정확히 하나의 우정 그룹에 속해야 한다.
\(1\)부터 \(N\)까지의 각 \(x\)에 대해, 만들어질 수 있는 우정 그룹의 최소 개수를 계산하여라.
문제 제공: Chongtian Ma
배점
- 입력 2-3: \(N\le 5000\)
- 입력 4-7: 모든 \(i\)에 대해 \(a_i\le 10\)
- 입력 8-11: 어떤 라벨도 \(10\)번을 초과하여 나타나지 않는다.
- 입력 12-20: 추가 제약 없음.
문제 제공: Chongtian Ma
첫째 줄에 정수 \(N\)이 주어진다.
다음 줄에 각 소의 라벨 \(a_1 ... a_N\)이 주어진다.
\(1\)부터 \(N\)까지의 각 \(x\)에 대해, 그 \(x\)에서의 우정 그룹의 최소 개수를 한 줄에 하나씩 출력한다.
9
1 1 1 9 2 1 2 1 17
5
4
4
4
4
4
3
3Here are examples of how to assign cows to friendship groups for \(x=1\) and \(x=2\)
in a way that minimizes the number of groups. Each letter corresponds to a
different group.
Example:
1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 groups)
x = 1: A A B C D E F G G (7 groups, alternative grouping)
x = 2: A A A B C D C E E (5 groups)
x = 2: A A A B C D C D E (5 groups, alternative grouping)
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Gold