問題一覧 > 通常問題

No.19 ステージの選択

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 161
作問者 : yuki2006yuki2006
8 ProblemId : 62 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:26

問題文

Naomiは、とあるアクションゲームをしている。

そのゲームでは、\(N\)個\((1\)から番号がふられている)のステージがありそれぞれ難易度が設定されている。
さらに、それぞれのステージは、先に指定されたステージをクリアしていると難易度が半分になるという仕組みになっている。

選んだステージは必ずクリアできるとし、すべてのステージをクリアすると考える。
この時、任意の順番でステージを選べるとして、各ステージの難易度の合計が最小になるように、ステージを選ぶとしたとき、その難易度の合計を求めてください。

答えは小数になることもあるが、小数第一位まで求めるとして、丸め誤差などの誤差はないように求めてください。

入力

\(N\)
\(L_1\ S_1\)
\(L_2\ S_2\)
\(\dots\)
\(L_i\ S_i\)
\(\dots\)
\(L_N\ S_N\)

$1$行目には、そのゲームのステージ数を表す整数値\(N\ (1 \leq N \leq 100)\)が与えられます。
\(2\)行目以降の、各\(i\ (1 \leq i \leq N)\)行目は\(i\)番目のステージの特徴を表している。
難易度を表す整数値\(L_i\ (1 \leq L_i \leq 100)\)とすでにクリアしていると難易度が半分になるステージの番号\(S_i\ (1 \leq S_i \leq N)\)が半角スペース区切りで与えられる。

出力

答えの数値を文字列として出力してください。
答えは小数になることもあるが、小数第一位まで求めるとして、丸め誤差などの誤差はないように求めてください。
最後に改行してください。

サンプル

サンプル1
入力
3
5 2
8 3
3 1
出力
9.5

\(3\)つステージがある。
ステージ\(1\)は 難易度\(5\)ですでにステージ\(2\)をクリアしていると難易度が\(2.5\)になる。
ステージ\(2\)は 難易度\(8\)ですでにステージ\(3\)をクリアしていると難易度が\(4\)になる。
ステージ\(3\)は 難易度\(3\)ですでにステージ\(1\)をクリアしていると難易度が\(1.5\)になる。

この時、初めにステージ\(3\)からはじめ、\(2,1\)とクリアしていくと難易度の合計が最小の\(9.5\)となる。

サンプル2
入力
2
4 2
4 1
出力
6.0

整数の場合でも小数第一位まで出力してください。

サンプル3
入力
5
5 1
8 3
3 2
6 5
9 4
出力
22.5

ステージ\(1\)は、自身をクリアしていると難易度が下がるが、1度クリアすればいいのでこの場合特に意味はない。

クリアの順は左から\([1,3,2,4,5]\)や\([4,5,3,2,1]\)とクリアしていくと最小の\(22.5\)となる。

サンプル4
入力
15
1 2
2 1
3 3
4 6
5 4
6 5
7 5
8 7
9 7
10 7
11 15
12 14
13 15
14 11
15 15
出力
71.5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。