← 返回题目列表

AtCoder · joi2007ho_e

E. 最轻的手机

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

最軽量のモビール - 原题 PDF 第 1 页
原题PDF第12页
最軽量のモビール - 原题 PDF 第 2 页
原题PDF第13页
最軽量のモビール - 原题 PDF 第 3 页
原题PDF第14页
可复制的 PDF 提取文本
5                 最軽量のモビール 


問題

  モビールは動く芸術品として広く親しまれている.IOI 日本委員会では,JOI を
 広報するためにモビールを作成することになった.JOI 広報用モビールは,棒,紐
(ひも),錘(おもり)の3 種類の要素を用いて,次のように構成される.

    • 棒の一方の端は青に,もう一方の端は赤に塗られている.

    • 棒は両端以外の1 箇所を支点として紐でつるされる.

    • 支点から赤の端までの長さも支点から青の端までの長さも正整数である.

    • 棒の両端には,紐で錘か他の棒をつるす.

    • 錘は紐を用いてどれかの棒の一端につるされる.

    • 錘には何もつるさない.

    • 錘の重さは正整数である.

    • 紐のうち1 本だけは,片方の端をある棒をつるすためにその棒の支点に結ばれ,
   もう一方の端は他のどの構成要素とも結ばれていない.他の紐は全て次のいず
   れかを満たす.

       – ある棒の端とある棒の支点を結ぶ.

       – ある棒の端とある錘を結ぶ.

ただし,どの棒においても,バランスが取れている必要がある.棒と紐の重さは無
視できるほど軽いので,棒と紐の重さは全て0 であるとみなして解答せよ.つまり,
それぞれの棒について,
   (その棒の赤の端より下につるされている錘の重さの総計)
   × (その棒の支点から赤の端までの長さ)
 = (その棒の青の端より下につるされている錘の重さの総計)
   ×  (その棒の支点から青の端までの長さ)
であるとき,その棒はバランスが取れているとせよ.





                        問題5-1

6
                                                         9
              6           9

                                         2

         3                       2                              3

                    バランスが取られていないので       簡単なモビールの例
                       モビールではない例

          4         4                         4         4

    1   3            3     2            1   3            3     2



   15      5      8                    15      5      8         2                           2    2                                                                    2


                                                              5
                         6         6
                                                                      7
      モビールの例           モビールではない例


 どのような長さの棒をどのように結びモビールを構成するかは既に決まっている
のだが,錘の重さがまだ決まっていない.モビールは軽い方がつりやすいため, なる
べく軽いモビールを作りたい.前述したようにどの棒もバランスを取りながら, モ
ビールの総重量を最小にするような錘の付け方を求め, そのときのモビールの総重量
を出力するプログラムを作れ. プログラムには以下のモビールの構成に関する情報
が与えられる.

   • 棒の本数n

   • 各棒ごとの情報(棒の番号は1 からn)

      – 支点から赤の端までの長さと支点から青の端までの長さの比

      – 赤の端につるす棒の番号(錘をつるす場合は0)

      – 青の端につるす棒の番号(錘をつるす場合は0)


           6           9                       6           9

        棒番号1             棒番号1

      3                       2           9                       6


   この構成で最軽量のモビール      最軽量ではないモビール


                        問題5-2

入力

 入力ファイルのファイル名はinput.txt である.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 < 231 を
満たす.


出力

 出力ファイルのファイル名はoutput.txt である.
  output.txt は1 行だけであり,モビールの重量を出力する.


入出力の例

入出力の例1

input.txt

     1
     6 9 0 0

output.txt

     5


入出力の例2

input.txt

     4
     3 2 0 4
     1 3 0 0
     4 4 2 1
     2 2 0 0

output.txt

     40


                        問題5-3