사발 쌓기

시간 제한1초메모리 제한128 MB

요약
그릇 n개를 원뿔대로 모델링해 쌓는 순서를 정해 전체 높이를 최소화하고 그 값의 정수 부분을 구하는 문제입니다.
난이도

어려움10점 중 8점

유형
기하, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

각 사발은 높이가 h이고, 밑면 반지름이 r, 윗면 반지름이 R인 원뿔대 모양이다. 윗면은 열려 있고 옆면은 직선이며, 사발의 두께는 무시한다. N개의 사발을 중심축이 같도록 포개어 쌓을 때, 전체 높이가 가능한 한 작아지도록 순서를 정하려고 한다. 만들 수 있는 최소 높이를 구하라.

입력

첫째 줄에 사발의 개수 n이 주어진다. 다음 n개의 줄에는 각 사발의 정보 h, r, R이 공백으로 구분되어 주어진다. h는 높이, r은 밑면 반지름, R은 윗면 반지름이다.

출력

첫째 줄에 가능한 최소 높이를 출력한다. 실제 최소 높이에서 소수점 아래를 버린 정수값을 출력한다.

제한

  • 2 ≤ n ≤ 9
  • 0 < h, r, R < 1000
  • r < R

예제1

  1. 예제 1

    입력
    3
50 30 80
35 25 70
40 10 90
    예상 출력
    55