Cow Checkups
브론즈 II의견: 0
*Note: We suggest using a language other than Python to earn full credit on this problem.*
Farmer John's \(N\) (\(1 \leq N \leq 7500\)) cows are standing in a line, with cow
\(1\) at the front of the line and cow \(N\) at the back of the line. FJ's cows also
come in many different species. He denotes each species with an integer from \(1\)
to \(N\). The \(i\)'th cow from the front of the line is of species \(a_i\)
(\(1 \leq a_i \leq N\)).
FJ is taking his cows to a checkup at a local bovine hospital. However, the
bovine veterinarian is very picky and wants to perform a checkup on the \(i\)'th
cow in the line, only if it is of species \(b_i\) (\(1 \leq b_i \leq N\)).
FJ is lazy and does not want to completely reorder his cows. He will perform
the following operation exactly once.
- Select two integers \(l\) and \(r\) such that \(1 \leq l \le r \leq N\). Reverse the order of the cows that are between the \(l\)-th cow and the \(r\)-th cow in the line, inclusive.
FJ wants to measure how effective this approach is. For each \(c=0 \ldots N\),
help FJ find the number of distinct operations (\(l,r\)) that result in exactly
\(c\) cows being checked. Two operations (\(l_1,r_1\)) and (\(l_2,r_2\)) are different
if \(l_1 \neq l_2\) or \(r_1 \neq r_2\).
Problem credits: Chongtian Ma and Haokai Ma
SCORING
- Inputs 4-6: \(N\le 100\)
- Inputs 7-13: No additional constraints
Problem credits: Chongtian Ma and Haokai Ma
The first line contains an integer \(N\).
The second line contains \(a_1, a_2, \ldots, a_N\).
The third line contains \(b_1, b_2, \ldots, b_N\).
Output \(N+1\) lines with the \(i\)-th line containing the number of distinct
operations (\(l,r\)) that result in \(i-1\) cows being checked.
3
1 3 2
3 2 13
3
0
0If FJ chooses (\(l=1,r=1\)), (\(l=2,r=2\)), or (\(l=3,r=3\)) then no cows will be
checked. Note that those operations do not modify any of the cows' locations.
The following operations result in one cow being checked.
- \(l=1,r=2\): FJ reverses the order of the first and second cows so the species of each cow in the new lineup will be \([3,1,2]\). The first cow will be checked.
- \(l=2,r=3\): FJ reverses the order of the second and third cows so the species of each cow in the new lineup will be \([1,2,3]\). The second cow will be checked.
- \(l=1,r=3\): FJ reverses the order of the first, second, and third cows so the species of each cow in the new lineup will be \([2,3,1]\). The third cow will be checked.
3
1 2 3
1 2 30
3
0
3The three possible operations that cause \(3\) cows to be checked are (\(l=1,r=1\)),
(\(l=2,r=2\)), and (\(l=3,r=3\)).
7
1 3 2 2 1 3 2
3 2 2 1 2 3 10
6
14
6
2
0
0
0The two possible operations that cause \(4\) cows to be checked are (\(l=4,r=5\))
and (\(l=5,r=7\)).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Bronze
평가 및 의견
Cow Checkups
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cow Checkups