23021번 - 등산로
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 42 | 20 | 13 | 43.333% |
문제
Albert는 등산을 즐겨한다.
Albert의 집 근처에는 동쪽과 서쪽에 각각 큰 산이 있고, 다양한 길이의 등산로가 마련되어있다.
동쪽 산에는 n개의 등산로가 있고 (편의상 이들의 길이를 A[1], ..., A[n]이라 하자) 서쪽 산에는 m개의 등산로가 있다 (편의상 이들의 길이를 B[1], ..., B[m]이라 하자).
동쪽 산의 n개의 등산로는 모두 같은 곳 (동쪽 산 출입구) 에서 시작하여 같은 곳에서 끝나고, 마찬가지로 서쪽 산의 m개의 등산로도 모두 같은 곳 (서쪽 산 출입구)에서 시작하여 같은 곳에서 끝난다.
동쪽 산과 서쪽 산의 입구는 길이가 x인 별도의 "동서 다리"를 통해 연결되어있다. 아래 그림에서 동쪽 산의 출입구는 정사각형으로, 서쪽 산의 출입구는 원으로 표시되어있고 두 출입구를 잇는 동서 다리의 길이는 x = 10 이다. 동쪽 산의 두 등산로의 길이는 각각 40과 45이고 서쪽 산의 두 등산로의 길이는 42로 동일하다.
Albert는 아래와 같은 규칙에 따라 총 길이가 C이상 D이하가 되도록 등산 계획을 세우고 싶다: (등산 계획은 어떤 등산로를 어떤 순서로 이용하는지 나타낸다)
- 같은 등산로는 최대 한 번만 이용한다.
- 같은 산의 등산로는 연속으로 이용하지 않는다 (즉, 동쪽 산과 서쪽 산의 등산로를 번갈아 이용한다).
- 어떤 산에서 다른 산으로 이동할 때에는 반드시 길이가 x인 동서 다리를 이용하며, 다른 길은 없다 (동서 다리는 여러 번 이용해도 된다).
- 동서 다리는 등산 계획의 맨 처음이나 맨 끝에 올 수 없고, 동서 다리는 연속으로 이용할 수 없다. 따라서 동서 다리를 이용할 경우 반드시 전/후에 동쪽 산 혹은 서쪽 산의 등산로를 이용해야 한다.
예를 들어, 위의 그림의 경우 n = m = 2, x = 10, A = [40, 45] 그리고 B = [42, 42] 이다. 이 때, C = 1, D = 100 이라 하자. 상기한 모든 규칙을 만족하며 길이가 1이상 100이하인 등산 계획은 총 12가지 있다:
- 총 길이가 40이상 45이하인 등산 계획은 4가지 존재한다 (네개의 등산로 중 하나를 이용하면 된다).
- 총 길이가 92이상 97이하인 등산 계획은 8가지 존재한다 (각 산에서 등산로 하나씩을 택한 후, 등산할 순서를 정하면 된다).
입력으로 n, m, x, C, D, 그리고 A, B가 주어졌을 때, Albert를 도와 총 몇가지 방법으로 등산 계획을 세울 수 있는지 구해보자.
입력
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 세줄에 걸쳐 주어진다.
첫 줄에는 n, m, x, C, D가 공백으로 구분되어 주어진다.
둘째 줄에는 동쪽 하이킹 코스 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
셋째 줄에는 서쪽 하이킹 코스 길이를 나타내는 m개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 정답이 매우 클 수 있으므로 109+7로 나눈 나머지를 출력한다.
제한
- 1 ≤ T ≤ 5
- 1 ≤ n, m ≤ 18
- 1 ≤ x ≤ 108
- 1 ≤ C ≤ D ≤ 109
- 1 ≤ 각 등산로의 길이 ≤ 108
예제 입력 1
3 3 5 100 245 245 10 20 30 1 2 3 4 5 5 5 1 39 39 1 2 3 4 5 5 4 3 2 1 5 5 1 1 3 1 1 1 1 1 1 1 1 1 1
예제 출력 1
2 28800 60
예제 1: 위 규칙을 만족하며 길이가 245인 등산 계획은 두 가지가 있다:
- 방법 1: (등산로 A1) - (다리) - (등산로 B5) - (다리) - (등산로 A3)
- 방법 2: (등산로 A3) - (다리) - (등산로 B5) - (다리) - (등산로 A1)
예제 2: 모든 10개의 등산로를 한 번씩 다 이용하면 (따라서 다리를 9번 지나면) 총 길이가 39가 된다.
위 규칙을 따르면서 10개의 등산로를 한 번씩 이용하는 방법은 총 28800가지가 있다.
예제 3:
- 총 길이가 1인 등산 계획은 10가지 존재한다 (아무 등산로 하나를 고르면 된다).
- 총 길이가 2인 등산 계획은 0가지 존재한다.
- 총 길이가 3인 등산 계획은 50가지 존재한다 (동쪽 산과 서쪽 산의 등산로 하나씩을 고르면 된다).
따라서 답은 60이다.
예제 입력 2
3 2 2 10 1 100 45 40 42 42 16 16 10 100 100 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 18 18 100000000 900000000 900000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
예제 출력 2
12 0 2996352
예제 1: 본문에서 다루었다.
예제 2-3: 추가 설명 없음.
시간 제한
- PyPy3: 6 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호