3307번 - 대회가 끝나고 난 뒤 빰빠빰 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 436 | 98 | 51 | 24.171% |
문제
CEOI 2011 준비를 끝내니 파티를 열고 싶어졌다. 사실 파티보다는 풍선이 불고 싶다. n개의 풍선이 있고, 모두 완전한 공모양 풍선이며 바닥에 놓여져 있다.
풍선에는 아직 바람을 넣지 않아서, 각 풍선의 반지름은 0에서 시작한다. 덧붙여, i번째 풍선은 xi좌표에 착 붙어 있어 움직이지도 공중에 떠오르지도 않는다. 각 풍선은 왼쪽에서 오른쪽 순서대로 바람을 넣는다. 그 풍선은 반지름의 한계까지 (ri에 다다를 때까지) 점점 늘어나거나, 혹은 이전에 부풀린 다른 풍선과 맞닿을 때까지 늘어난다.
그림 1 : 예제의 풍선을 모두 부풀린 모습이다.
풍선을 모두 부풀리기 위해서 공기가 얼마나 필요한지 알고 싶다. 각 풍선들의 최종 반지름을 구하라.
입력
첫 번째 줄에 풍선의 개수 n이 주어진다 (1 ≤ n ≤ 200 000). 이어지는 n개의 줄에는 풍선에 대한 정보가 주어진다.
각 i번째 줄에는 xi와 ri 두 개의 정수가 주어진다. (풍선이 놓여 있는 x축 좌표 0 ≤ xi ≤ 109, 풍선의 반지름의 최댓값 1 ≤ ri ≤ 109). 각 풍선들의 위치인 x좌표는 반드시 오른쪽으로만 나아간다.
출력
결과값은 반드시 n개의 줄로 출력되어야 하며, i번째 줄에는 정확히 i번째 풍선의 최종 반지름만 출력되어야 한다. 0.001 이하의 오차는 허용된다.
예제 입력 1
3 0 9 8 1 13 7
예제 출력 1
9.000 1.000 4.694
출처
Olympiad > Central European Olympiad in Informatics > CEOI 2011 > Day 1 1번
- 문제를 번역한 사람: pty115
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호