Cowdependence
다이아몬드 V의견: 0
Farmer John's \(N\) \((1 \leq N \leq 10^5)\) cows have been arranged into a line.
The \(i\)th cow has label \(a_i\) (\(1 \leq a_i \leq N\)). A group of cows can form a
friendship group if they all have the same label and each cow is within \(x\)
cows of all the others in the group, where \(x\) is an integer in the range
\([1,N]\). Every cow must be in exactly one friendship group.
For each \(x\) from \(1\) to \(N\), calculate the minimum number of friendship groups
that could have formed.
Problem credits: Chongtian Ma
SCORING
- Inputs 2-3: \(N\le 5000\)
- Inputs 4-7: \(a_i\le 10\) for all \(i\)
- Inputs 8-11: No label appears more than \(10\) times.
- Inputs 12-20: No additional constraints.
Problem credits: Chongtian Ma
The first line consists of an integer \(N\).
The next line contains \(a_1 ... a_N\), the labels of each cow.
For each \(x\) from \(1\) to \(N\), output the minimum number of friendship groups for
that \(x\) on a new line.
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
평가 및 의견
Cowdependence
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cowdependence