21984번 - 나무 징검다리 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 19 | 13 | 8 | 57.143% |
문제
Albert는 다양한 크기의 나무 밑둥 (stump) 모양의 장난감으로 징검다리를 만들고 싶어한다.
각 장난감은 1부터 n까지 번호가 붙어있고, i번째 장난감의 높이는 H[i] 이고 반지름은 R[i] 이다.
Albert는 n개의 나무 밑둥 장난감을 왼쪽에서 오른쪽으로 임의의 순서로 나열하되, 아래의 조건을 만족하도록 하고 싶다.
- 조건 1: 장난감의 높이는 1번째 밑둥부터 k번째 밑둥까지 강한 단조 증가 (strictly increasing) 수열을 이루며 k번째부터 n번째 까지는 강한 단조 감소 (strictly decreasing) 수열을 이룬다. 단, 이 때 k는 1 < k < n를 만족해야 한다.
- 조건 2: 장난감의 반지름은 왼쪽에서 오른쪽으로 감소, 증가, 감소, 증가, ..., 혹은 증가, 감소, 증가, 감소 해야한다. 즉, 인접한 두 장난감의 반지름이 반드시 달라야 하고, 반지름 차이는 감소와 증가가 번갈아 일어나야 한다.
예를 들어 n = 3, H = [10, 20, 30], 그리고 R = [2, 3, 4]라 하자.
- 장난감을 1번, 2번, 3번 순서로 나열하는 경우:
- 조건 1: 주어진 조건을 만족하는 k가 존재하지 않는다 (k = 3은 k < n 을 어김에 유의하자)
- 조건 2: 장난감의 반지름이 증가 (2에서 3), 증가 (3에서 4) 하므로 조건 2를 만족하지 않는다.
- 장난감을 1번, 3번, 2번 순서로 나열하는 경우:
- 조건 1: 처음 두 장난감의 높이는 단조 증가하고 마지막 두 장난감의 높이는 단조 감소 하므로 k = 2 일 때 조건 1을 만족한다.
- 조건 2: 장난감의 반지름이 2 -> 4 -> 3 으로 증가, 감소 하므로 조건 2를 만족한다.
- 장난감을 2번, 1번, 3번 순서로 나열하는 경우:
- 조건 1: 높이가 [20, 10, 30] 으로 강한 단조 감소 후 강한 단조 증가하는데 주어진 조건은 강한 단조 증가 후 강한 단조 감소이다 (따라서 조건1을 어긴다).
- 조건 2: 장난감의 반지름이 3 -> 2 -> 4로 감소, 증가 하므로 조건 2를 만족한다.
이 예제의 경우 상기한 (1번, 3번, 2번) 순서로 나열하는 경우 외에 (2번, 3번, 1번) 순서로 나열하는 경우도 두 조건을 만족한다.
다른 예로, n = 3, H = [10, 20, 30], 그리고 R = [2, 5, 2]라 하자.
이 경우, 세 장난감을 나열하는 6가지 방법 중 상기한 두 조건을 모두 만족하는 경우는 없다.
마지막으로, n = 5, H = [10, 20, 30, 40, 50], R = [2, 7, 3, 4, 6] 이라 하자.
이 경우, 총 4가지 다른 방법으로 장난감을 나열하여 상기한 두 조건을 만족시킬 수 있다.
- 장난감을 1번 2번 3번 5번 4번 순서로 나열한 경우:
- 조건 1: 높이가 [10, 20, 30, 50, 40] 으로 k = 4 일 때 조건을 만족한다.
- 조건 2: 반지름이 [2, 7, 3, 6, 4]로 증가, 감소, 증가, 감소 하므로 조건을 만족한다. 본문의 그림은 이 예제에서 장난감을 1-2-3-5-4번 순서로 나열한 경우를 나타낸다.
- 장난감을 1번 2번 4번 5번 3번 순서로 나열한 경우:
- 조건 1: 높이가 [10, 20, 40, 50, 30] 으로 k = 4 일 때 조건을 만족한다.
- 조건 2: 반지름이 [2, 7, 4, 6, 3]로 증가, 감소, 증가, 감소 하므로 조건을 만족한다.
- 그 외에 장난감을 3번 5번 4번 2번 1번 순서로 나열한 경우와 4번 5번 3번 2번 1번 순으로 나열한 경우가 가능하다.
입력으로 n과 각 장난감의 높이/반지름이 주어졌을 때, 위의 두 조건을 만족하며 장난감을 나열할 수 있는 방법이 있는지 알아보자.
입력
첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 세 줄에 나누어 주어진다.
첫 줄에는 n이 주어진다.
둘째 줄에는 장난감의 높이 (H[i])를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
셋째 줄에는 장난감의 반지름 (R[i])을 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대하여 답을 한 줄에 출력한다.
조건을 만족하는 장난감 나열법이 있을 경우, n개의 장난감 번호를 공백으로 구분하여 출력한다. 본문의 예제 처럼 다양한 답이 존재하는 경우, 아무 것이나 한 가지 방법을 출력하면 된다. 조건을 만족하는 방법이 없을 경우 -1을 출력한다.
제한
- 1 ≤ T ≤ 20
- 1 < n ≤ 400
- 1 ≤ H[i], R[i] ≤ 1,000,000,000
서브태스크 1 (10점)
- 1 ≤ n ≤ 15
서브태스크 2 (20점)
- 1 ≤ n ≤ 400
예제 입력 1
8 3 10 20 30 2 5 2 3 10 20 30 2 3 4 5 10 20 30 40 50 2 7 3 4 6 3 2 4 5 6 1 4 3 1 2 3 2 6 2 5 1 1 2 6 7 4 6 4 2 8 5 2 6 4 4 8 6 4 2 5 1 5 1 2 3 4 5 2 7 6 4 3
예제 출력 1
-1 1 3 2 1 2 3 5 4 -1 -1 2 3 5 4 1 4 5 2 3 1 -1
예제 1-3: 본문에서 다루었다.
예제 4-예제8: 추가 설명 없음.
시간 제한
- Java 8: 3 초
- PyPy3: 7 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호