시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 235 | 46 | 39 | 27.273% |
저출산 때문에 가장 큰 고통을 받고 있는 산업분야라고 하면 역시 교육을 뽑을 수 있겠다.
점점 줄어들어만 가는 학생들 때문에 너도나도 앞장서서 자신만의 독특한 교육 아이템을 광고하곤 하는데, 이는 2D 나라에 있는 일루 유치원 역시 예외가 아니었다.
일루 유치원에서는 재학생들을 위한 놀이 활동이자 신입생 유치의 일환으로 특대형 이진 모빌 만들기에 도전하고자 한다.
일루 유치원에서 만들고자 하는 이진 모빌은 아래와 같은 모양새를 띄고 있다.
한 편, 일루 원장선생님은 모빌을 전시하기 위한 공간 확보에 어려움을 겪고 있었다. 재료들은 있지만 완성된 모빌의 크기가 얼마나 될지 알 수가 없었기 때문이다.
일루 원장님의 절친한 친구인 당신은 그의 유치원 경영을 도와주고자 한다. 나무 막대들과 구슬간의 연결 상태가 주어질 때, 주어진 모빌의 가로 너비를 출력하는 프로그램을 작성하라.
첫 줄에는 테스트 케이스의 수 \(T\)가 주어진다.
각 테스트 케이스의 첫 줄에는 나무 막대의 수 \(n(1 \leq n \leq 100,000)\)이 주어진다. 다음 \(n\) 개의 줄에 각 나무 막대의 길이를 나타내는 정수 \(len\) (\(1 \leq len \leq 1,000\))과 왼쪽 / 오른쪽 실의 반대편에 매달린 물체의 정보를 나타내는 두 정수 \(l, r\)이 공백으로 구분되어 주어진다. \(-n \leq l \leq -1\) 일 경우에는 \(-l\) 번 나무막대가 왼쪽 끝에 달려 있다는 뜻이며, \(1 \leq l \leq 100,000\)일 경우에는 왼쪽 끝에 해당 중량의 구슬이 달려있다는 뜻이다. \(r\) 역시 오른쪽 끝에 달려있는 정보를 표기한다는 점을 제외하면 \(l\)과 같이 이해하면 된다.
입력으로는 나무 막대와 구슬간의 연결상태, 각 나무 막대의 길이, 각 구슬의 중량이 주어진다.
모든 막대는 한 연결된 컴포넌트의 구성원임이 보장된다.
각 테스트 케이스당 한 줄에 걸쳐 모빌의 폭을 출력한다.
\(10^{-6}\) 이하의 절대 / 상대오차는 정답으로 인정한다.
1 3 10 -2 -3 2 100 50 8 75 75
14.66666666666
예제를 그림으로 그리면 다음과 같다.
Contest > Coder's High > Coder's High 2015 Side Contest B1번