#PU1469. USACO 2025 January Contest, Bronze — Problem 3. Cow Checkups
USACO 2025 January Contest, Bronze — Problem 3. Cow Checkups
USACO 2025 January Contest, Bronze — Problem 3. Cow Checkups
题目描述
Note: We suggest using a language other than Python to earn full credit on this problem. Farmer John's () cows are standing in a line, with cow at the front of the line and cow at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from to . The 'th cow from the front of the line is of species (). 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 'th cow in the line, only if it is of species (). FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once . Select two integers and such that . Reverse the order of the cows that are between the -th cow and the -th cow in the line, inclusive. FJ wants to measure how effective this approach is. For each , help FJ find the number of distinct operations () that result in exactly cows being checked. Two operations () and () are different if or .
输入格式
The first line contains an integer . The second line contains . The third line contains .
输出格式
(见题面原文)
数据范围
Inputs 4-6: Inputs 7-13: No additional constraints Problem credits: Chongtian Ma and Haokai Ma
样例
样例 1
3
1 3 2
3 2 1
3
3
0
0
If 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.
样例 2
3
1 2 3
1 2 3
0
3
0
3
The three possible operations that cause $3$ cows to be checked are ($l=1,r=1$),
($l=2,r=2$), and ($l=3,r=3$).
样例 3
7
1 3 2 2 1 3 2
3 2 2 1 2 3 1
0
6
14
6
2
0
0
0
The two possible operations that cause $4$ cows to be checked are ($l=4,r=5$)
and ($l=5,r=7$).