5216 : A17 - 던전 2
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
어느 던전에는 $N$ 개의 방이 있으며, 1번부터 $N$ 번까지 번호가 매겨져 있습니다. 이 던전은 일방통행이며, 통로를 통해 1칸 앞 또는 2칸 앞의 방으로 이동할 수 있습니다. 각 통로의 이동 시간은 다음과 같습니다.
타로가 방 1에서 방 $N$ 으로 최단 시간으로 이동하는 방법을 하나 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $3 ≤ N ≤ 100\,000$
• $1 ≤ A_i ≤ 100$ ($2 ≤ i ≤ N$)
• $1 ≤ B_i ≤ 100$ ($3 ≤ i ≤ N$)
• 입력되는 모든 값은 정수입니다.
- 방 $i - 1$ 에서 방 $i$ 로 가는 통로를 통과하는 데 $A_i$ 분이 걸린다 ($2 \le i \le N$).
- 방 $i - 2$ 에서 방 $i$ 로 가는 통로를 통과하는 데 $B_i$ 분이 걸린다 ($3 \le i \le N$).
타로가 방 1에서 방 $N$ 으로 최단 시간으로 이동하는 방법을 하나 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $3 ≤ N ≤ 100\,000$
• $1 ≤ A_i ≤ 100$ ($2 ≤ i ≤ N$)
• $1 ≤ B_i ≤ 100$ ($3 ≤ i ≤ N$)
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$ 이 주어집니다.
둘째 줄에 $A_2, A_3, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
셋째 줄에 $B_3, B_4, \dots, B_N$ 이 공백으로 구분되어 주어집니다.
둘째 줄에 $A_2, A_3, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
셋째 줄에 $B_3, B_4, \dots, B_N$ 이 공백으로 구분되어 주어집니다.
출력 설명
첫째 줄에 방문하는 방의 개수 $P$ 를 출력하십시오.
둘째 줄에 방문하는 방의 번호를 방 1부터 방 $N$ 까지 순서대로 공백으로 구분하여 출력하십시오.
둘째 줄에 방문하는 방의 번호를 방 1부터 방 $N$ 까지 순서대로 공백으로 구분하여 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
2 4 1 3
5 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 2 4 5