레이팅 미적용농부 존에게는 키가 \(a_1 \ldots a_N\)인 소 \(N\)마리(\(1\le N \leq 20\))가 있다. 그의 외양간에는 최대 높이 제한이 \(b_1 \ldots b_N\)인 \(N\)개의 축사가 있다(예를 들어 \(b_5 = 17\)이면 키가 최대 \(17\)인 소가 축사 \(5\)에 들어갈 수 있다). 각 소가 서로 다른 축사에 들어가고 모든 축사의 높이 제한이 지켜지도록 농부 존이 소들을 배치하는 서로 다른 방법은 몇 가지인가?
문제 제공: Shreyas Thumathy
배점
- 테스트 케이스 1-5는 \(N\le 8\)을 만족한다.
- 테스트 케이스 6-12에는 추가 제약이 없다.
문제 제공: Shreyas Thumathy
첫째 줄에 \(N\)이 주어진다. 둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(a_1,a_2,\ldots,a_N\)이 주어진다. 셋째 줄에 공백으로 구분된 \(N\)개의 정수 \(b_1,b_2,\ldots,b_N\)이 주어진다. 모든 키와 제한은 \([1,10^9]\) 범위에 있다.
모든 축사의 높이 제한이 지켜지도록 각 소를 서로 다른 축사에 배치하는 방법의 수를 출력한다. 출력값이 클 수 있으므로 C++의 "long long"과 같은 64비트 정수가 필요할 수 있음에 유의한다.
4
1 2 3 4
2 4 3 48In this example, we cannot place the third cow into the first stall since
\(3=a_3>b_1=2\). Similarly, we cannot place the fourth cow into the first or
third stalls. One way to satisfy the height limits is to assign cow \(1\) to stall
\(1\), cow \(2\) to stall \(2\), cow \(3\) to stall \(3\), and cow \(4\) to stall \(4\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Bronze