닭장에 닭 배치하기

실행 시간 제한	메모리 제한
1 초	512 MB

📃 해결할 문제

농부 철수는 N ( $1 \le N \leq 20$ ) 마리의 닭을 키우고 있습니다. 닭들의 키는 $a_1 \ldots a_N$ 입니다.

철수는 N개의 닭장이 있으며, 각 닭장마다 닭이 들어갈 수 있는 최대 높이 제한은 $b_1 \ldots b_N$ 입니다.

(예를 들어 $b_5 = 17$ 이라면, 키가 17이하인 닭은 다섯 번째 닭장에 들어갈 수 있습니다.)

모든 닭이 각 닭장의 키 제한에 맞게 서로 다른 닭장에 들어간다는 조건 하에, 철수가 모든 닭을 닭장에 배치할 수 있는 서로 다른 방법은 총 몇 가지인가요?

💻 입력

첫 번째 줄에는 $N$ 이 주어집니다. 두 번째 줄에는 $N$ 개의 공백으로 구분된 정수 $a_1, a_2, \ldots, a_N$ 이 주어집니다. 세 번째 줄에는 $N$ 개의 공백으로 구분된 정수 $b_1, b_2, \ldots, b_N$ 이 주어집니다. 모든 높이와 제한은 $[1,10^9]$ 범위에 있습니다.

🖨️ 출력

농부 철수가 각 닭을 다른 닭장에 배치하는 방법의 수를 구합니다. 이 때, 각 닭장에는 높이 제한이 존재하며, 모든 닭장에 대해 높이 제한이 지켜져야합니다. 출력값이 매우 클 수 있으므로, C++의 "long long"과 같은 64비트 정수를 사용해야 할 수 있습니다.

💻 예제 입력 1

4
1 2 3 4
2 4 3 4

🖨️ 예제 출력 1

💡 힌트

이 예시에서, $3=a_3$ 이므로 세 번째 닭은 첫 번째 닭장에 배치할 수 없습니다. (왜냐하면 $3=a_3 \gt b_1=2$ 이기 때문입니다)

마찬가지로, 네 번째 닭은 첫 번째 또는 세 번째 닭장에 배치할 수 없습니다. 높이 제한을 만족하는 한 가지 방법은 닭 $1$ 을 닭장 $1$ 에, 닭 $2$ 를 닭장 $2$ 에, 닭 $3$ 을 닭장 $3$ 에, 닭 $4$ 를 닭장 $4$ 에 배치하는 것입니다.

점수:

- 테스트 케이스 1-5는 $N \le 8$ 을 만족합니다.

- 테스트 케이스 6-12는 추가적인 제약 조건을 만족시키지 않습니다.

출처: USACO 2021 January Contest, Bronze Problem 3. Just Stalling