Bessie's Function
플래티넘 I의견: 0
Bessie has a special function \(f(x)\) that takes as input an integer in \([1, N]\)
and returns an integer in \([1, N]\) (\(1 \le N \le 2 \cdot 10^5\)). Her function
\(f(x)\) is defined by \(N\) integers \(a_1 \ldots a_N\) where \(f(x) = a_x\)
(\(1 \le a_i \le N\)).
Bessie wants this function to be idempotent. In other words, it should satisfy
\(f(f(x)) = f(x)\) for all integers \(x \in [1, N]\).
For a cost of \(c_i\), Bessie can change the value of \(a_i\) to any integer in
\([1, N]\) (\(1 \le c_i \le 10^9\)). Determine the minimum total cost Bessie needs
to make \(f(x)\) idempotent.
Problem credits: Avnith Vijayram
SCORING
Subtasks:
- Input 3: \(N\le 20\)
- Inputs 4-9: \(a_i\ge i\)
- Inputs 10-15: All \(a_i\) are distinct.
- Inputs 16-21: No additional constraints.
Additionally, in each of the last three subtasks, the first half of tests will
satisfy \(c_i=1\) for all \(i\).
Problem credits: Avnith Vijayram
The first line contains \(N\).
The second line contains \(N\) space-separated integers \(a_1,a_2,\dots,a_N\).
The third line contains \(N\) space-separated integers \(c_1,c_2,\dots,c_N\).
Output the minimum total cost Bessie needs to make \(f(x)\) idempotent.
5
2 4 4 5 3
1 1 1 1 13We can change \(a_1 = 4\), \(a_4 = 4\), \(a_5 = 4\). Since all \(c_i\) equal one, the
total cost is equal to \(3\), the number of changes. It can be shown that there is
no solution with only \(2\) or fewer changes.
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 97We change \(a_3 = 3\) and \(a_4 = 4\). The total cost is \(2+5=7\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Gold
평가 및 의견
Bessie's Function
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bessie's Function