시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 25 | 18 | 17 | 70.833% |
モビールは動く芸術品として広く親しまれている.IOI 日本委員会では,JOI を 広報するためにモビールを作成することになった.JOI 広報用モビールは,棒,紐 (ひも),錘(おもり)の 3 種類の要素を用いて,次のように構成される.
ただし,どの棒においても,バランスが取れている必要がある.棒と紐の重さは無 視できるほど軽いので,棒と紐の重さは全て 0 であるとみなして解答せよ.つまり, それぞれの棒について,
(その棒の赤の端より下につるされている錘の重さの総計) × (その棒の支点から赤の端までの長さ)=(その棒の青の端より下につるされている錘の重さの総計) × (その棒の支点から青の端までの長さ)
であるとき,その棒はバランスが取れているとせよ.
簡単なモビールの例 | バランスが取られていないので モビールではない例 |
モビールの例 | モビールではない例 |
どのような長さの棒をどのように結びモビールを構成するかは既に決まっている のだが,錘の重さがまだ決まっていない.モビールは軽い方がつりやすいため, なる べく軽いモビールを作りたい.前述したようにどの棒もバランスを取りながら, モ ビールの総重量を最小にするような錘の付け方を求め, そのときのモビールの総重量 を出力するプログラムを作れ. プログラムには以下のモビールの構成に関する情報 が与えられる.
この構成で最軽量のモビール | 最軽量ではないモビール |
問題 5-2
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 を 満たす.
1 行だけであり,モビールの重量を出力する.
1 6 9 0 0
5
4 3 2 0 4 1 3 0 0 4 4 2 1 2 2 0 0
40