dlaud5379   1년 전

(DeepL로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

모빌은 움직이는 예술품으로 널리 알려져 있다. IOI 일본위원회에서는 JOI를 홍보하기 위해 모빌을 제작하게 되었고, JOI 홍보용 모빌은 막대, 끈, 추의 3가지 요소를 사용하여 다음과 같이 구성한다.

  • 막대의 한쪽 끝은 파란색, 다른 쪽 끝은 빨간색으로 칠해져 있다.
  • 막대는 양 끝이 아닌 한 지점에 끈으로 매달려 있다.
  • [끈으로 매달린] 지점에서 빨간색 끝까지의 길이와 지점에서 파란색 끝까지의 길이는 모두 양의 정수이다.
  • 막대의 양 끝에는 끈으로 추 또는 다른 막대를 매단다.
  • 추는 어떤 막대의 한쪽 끝에 끈으로 매달린다.
  • 추에는 아무것도 매달지 않는다.
  • 추의 무게는 양의 정수이다.
  • 끈 중 하나는 한쪽 끝이 어떤 막대의 한 지점에 묶여 있고, 다른 쪽 끝은 어떤 구성 요소와도 묶여 있지 않다. 나머지 모든 끈은 다음 중 하나를 만족한다.
    • 어떤 막대의 끝과 다른 막대의 지지점을 연결한다.
    • 어떤 막대의 끝과 어떤 추를 연결한다.

단, 모든 막대는 균형이 잡혀 있어야 한다. 막대와 끈의 무게는 무시할 수 있을 정도로 가벼우므로 막대와 끈의 무게는 모두 0으로 간주한다. 즉, 각 막대에 대해

(그 막대의 빨간색 끝에 매달려 있는 추의 무게의 총합) × (그 막대의 지점에서 빨간색 끝까지의 길이) = (그 막대의 파란색 끝에 매달려 있는 추의 무게의 총합) × (그 막대의 지점에서 파란색 끝까지의 길이)

일 때, 그 막대는 균형이 잡혀 있다고 하자.

previewpreview
간단한 모빌의 예시균형이 맞지 않아 모빌이 아닌 예시
previewpreview
모빌의 예시모빌이 아닌 예시

어떤 길이의 막대를 어떻게 묶어 모빌을 구성할지는 이미 정해졌지만, 추의 무게는 아직 정해지지 않았다. 모빌은 가벼울수록 매달리기 쉽기 때문에 가능한 한 가벼운 모빌을 만들려고 한다. 앞에서 설명한 것처럼 모든 막대의 균형을 유지하면서 모빌의 총 무게를 최소화할 수 있는 추의 무게를 구하고, 그때의 모빌의 총 무게를 출력하는 프로그램을 작성하여라. 프로그램에는 다음과 같은 모빌의 구성에 대한 정보가 주어진다.

  • 막대의 개수 n
  • 각 막대에 대한 정보 (막대의 번호는 1부터 n까지)
  • 지점에서 빨간색 끝까지의 길이와 지점에서 파란색 끝까지의 길이의 비율
  • 빨간색 끝에 매달릴 막대의 번호 (추를 매다는 경우는 0)
  • 파란색 끝에 매달릴 막대의 번호 (추를 매다는 경우는 0)
previewpreview
주어진 구성에서 가장 가벼운 모빌
(이미지 내 텍스트: '막대 번호 1')
가장 가볍지 않은 모빌

입력

첫째 줄에 모빌에 사용되는 막대의 개수 n이 주어진다. 이어지는 n줄(1 ≤ n ≤ 100)에는 각 막대의 정보가 주어진다. i + 1번째 줄(1 ≤ i ≤ n)에는 4개의 정수 p, q, r, b가 공백으로 구분되어 주어지며, 막대 i에서 지점에서 빨간색 끝까지의 길이와 지점에서 파란색 끝까지의 길이의 비율이 p : q이고, 빨간색 끝에 매달리는 막대의 번호가 r이며, 파란색 끝에 매달리는 막대의 번호가 b라는 의미이다. 단, 막대 번호 0은 추가 매달려 있다는 의미이다. 또한, 각 테스트 케이스에서 모빌의 무게의 최솟값을 w, 입력에서 비율을 나타내는 데 쓰인 양의 정수의 최댓값을 L이라 할 때 wL < 2^31을 만족한다.

출력

한 줄에 모빌의 무게를 출력한다.

댓글을 작성하려면 로그인해야 합니다.