레이팅 미적용*참고: 이 문제에서 만점을 받으려면 Python이 아닌 다른 언어를 사용할 것을 권장한다.*
농부 존의 \(N\)(\(1 \leq N \leq 7500\))마리 소들이 한 줄로 서 있다. 소 \(1\)이 줄의 맨 앞에, 소 \(N\)이 줄의 맨 뒤에 있다. 농부 존의 소들은 다양한 품종으로 이루어져 있다. 그는 각 품종을 \(1\)부터 \(N\)까지의 정수로 나타낸다. 줄의 앞에서 \(i\)번째 소의 품종은 \(a_i\)(\(1 \leq a_i \leq N\))이다.
농부 존은 소들을 데리고 지역 소 병원에 건강검진을 받으러 간다. 그런데 소 수의사가 매우 까다로워서, 줄의 \(i\)번째 소가 품종 \(b_i\)(\(1 \leq b_i \leq N\))일 때에만 그 소의 검진을 해 주려 한다.
농부 존은 게을러서 소들의 순서를 완전히 재배치하고 싶지는 않다. 그는 다음 연산을 정확히 한 번 수행할 것이다.
- \(1 \leq l \le r \leq N\)인 두 정수 \(l\)과 \(r\)을 선택한다. 줄에서 \(l\)번째 소부터 \(r\)번째 소까지(양 끝 포함)의 순서를 뒤집는다.
농부 존은 이 방법이 얼마나 효과적인지 측정하고 싶다. 각 \(c=0 \ldots N\)에 대해, 정확히 \(c\)마리의 소가 검진을 받게 되는 서로 다른 연산 (\(l,r\))의 개수를 찾도록 도와주자. 두 연산 (\(l_1,r_1\))과 (\(l_2,r_2\))는 \(l_1 \neq l_2\)이거나 \(r_1 \neq r_2\)이면 서로 다르다.
문제 제공: Chongtian Ma and Haokai Ma
배점
- 입력 4-6: \(N\le 100\)
- 입력 7-13: 추가 제약 없음
문제 제공: Chongtian Ma and Haokai Ma
첫째 줄에 정수 \(N\)이 주어진다.
둘째 줄에 \(a_1, a_2, \ldots, a_N\)이 주어진다.
셋째 줄에 \(b_1, b_2, \ldots, b_N\)이 주어진다.
\(N+1\)개의 줄을 출력한다. \(i\)번째 줄에는 정확히 \(i-1\)마리의 소가 검진을 받게 되는 서로 다른 연산 (\(l,r\))의 개수를 출력한다.
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