Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はプログラミングコンテストに参加しようとしています。このコンテストでは簡単な問題が N 問出題されます。高橋君は普段 1 問あたり A 分で解くことが出来ますが、ダイナミックなポーズをとりながら問題を解くことで 1 問あたり B 分で解くことが出来るようになります。ただし、ダイナミックなポーズには体力を著しく消耗してしまうので、1 回のプログラミングコンテストでは 5 問までしかダイナミックなポーズをとりながら解くことができません。高橋君は最短何分で N 問の問題を全て解くことが出来るでしょうか。
入力
入力は以下の形式で標準入力から与えられる。
N A B
- 1 行目には、問題数を表した整数 N (1 ≦ N ≦ 10) と、高橋君が普段 1 問の問題を解くためにかかる時間を分単位で表した整数 A (2 ≦ A ≦ 60) と、高橋君がダイナミックなポーズをとりながら 1 問の問題を解くためにかかる時間を分単位で表した整数 B (1 ≦ B < A) が空白区切りで与えられる。
出力
最短時間で高橋君が全ての問題を解いたときにかかる時間を分単位で表した整数 1 行に出力せよ。出力の末尾に改行をいれること。
入力例1
10 5 1
出力例1
30
このケースでは、5 問をダイナミックなポーズをとりながら解き、残りの 5 問を普段通りに解くことによって合計 30 分で全ての問題を解くことが出来ます。
入力例2
4 60 7
出力例2
28
このケースでは、全ての問題をダイナミックなポーズをとりながら解くことが出来ます。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は完全なものが大好きです。
自然数には、完全数というものがあります。 完全数というのは、自分以外の約数の総和が自分と等しくなる自然数のことです。 例えば 6 の場合 1 + 2 + 3 = 6となるので完全数です。 それに対して、自分以外の約数の総和が自分より小さくなる場合は不足数と言い、大きくなる場合は過剰数と言います。
高橋君には今気になっている自然数があります。高橋君のために、それが完全数なのか不足数なのか過剰数なのか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目に高橋君が気になっている自然数N (1 ≦ N ≦ 10^{10})が与えられる。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 10^5を満たすデータセットに正解した場合は 50 点が与えられる。
- 1 ≦ N ≦ 10^{10}を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。
出力
Nが完全数ならばPerfect、 不足数ならばDeficient、 過剰数ならばAbundant、を1行で出力せよ。
入力例1
6
出力例1
Perfect
1 + 2 + 3 = 6なので6は完全数です。
入力例2
24
出力例2
Abundant
1 + 2 + 3 + 4 + 6 + 8 + 12 > 24なので24は過剰数です。
入力例3
27
出力例3
Deficient
1 + 3 + 9 < 27なので27は不足数です。
入力例4
945
出力例4
Abundant
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある小学校には、すごく長い廊下があります。東西に伸びていて、西端から東端まで L メートルあります。 学校の方針で窓は一切ついていないので、蛍光灯で廊下を照らさなければいけません。
この廊下には N 個の蛍光灯がついています。 i 番目の蛍光灯は西端から l_i メートルの地点と r_i メートルの地点の間を照らすことができます。 また、蛍光灯によって点けるのに必要な費用が違います。 i 番目の蛍光灯を点けるには c_i 円の費用がかかります。
全ての蛍光灯を点ければ、廊下全体を照らすことは可能ですが、お金がないので可能な限り少ない費用で廊下全体を照らしたいです。 廊下のどの地点、つまり西端から 0 メートルの地点と L メートルの地点の間のどの地点も少なくとも1つ以上の蛍光灯に照らされているように蛍光灯を点けるとき、必要な費用の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N L l_1 r_1 c_1 l_2 r_2 c_2 : l_N r_N c_N
制約に不十分な記述があったため、修正しました。「蛍光灯の照らす範囲」→「蛍光灯の照らす範囲を表す整数」（21:20）
- 1 行目には蛍光灯の個数を表す整数 N (1 ≦ N ≦ 10^5) と廊下の長さを表すを表す整数L(1 ≦ L ≦ 10^5)が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目にはi番目の蛍光灯の照らす範囲を表す整数 l_i, r_i (0 ≦ l_i ＜ r_i ≦ L) と、点けるのにかかる費用 c_i (1 ≦ c_i ≦ 10^5) が空白区切りで与えられる。
- 全ての蛍光灯を点ければ、廊下全体を照らすことができることが保証されている。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 3,000 ,1 ≦ L ≦ 3,000を満たすデータセットに正解した場合は 60 点が与えられる。
- 1 ≦ N ≦ 10^5 ,1 ≦ L ≦ 10^5を満たすデータセットに正解した場合はさらに 40 点が与えられる。合計で100点となる。
出力
廊下全体を照らすのに必要な費用の最小値を1行で出力せよ。
入力例1
5 5 0 1 1 1 2 1 2 4 3 3 5 1 2 3 2
出力例1
5
1, 2, 4, 5番目の蛍光灯を点けた時、費用の総和が最小になります。
入力例2
8 10 0 2 1 2 3 1 0 4 1 0 2 1 3 7 1 0 10 1080 8 10 1 9 10 1
出力例2
1080
6番目の蛍光灯を点けない限り、西端から7メートルの地点と8メートルの地点の間は照らされません。 6番目の蛍光灯だけを使うのが、最適な点け方です。
入力例3
10 10 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 0 5 4 5 7 2 6 8 3 8 10 1 2 9 3
出力例3
6
入力例4
5 5 0 1 100000 1 2 100000 2 3 100000 3 4 100000 4 5 100000
出力例4
500000
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ダイナミック王国には N 個の村があり、0 から N-1 までの番号がついています。それらの村は M 本の道でひと繋がりになっていました。「ひと繋がりになっている」とは、どの村からどの村へもいくつかの道を辿って行くことが出来る状態のことを指します。ある日大規模な災害によって全ての道が壊れて、村と村の間の移動が出来なくなってしまいました。あなたは王様の高橋君から、道を修理してダイナミック王国の N 個の村をひと繋がりにする仕事を依頼されました。
あなたはまず、それぞれの道を修理するため必要な費用と時間を見積もりました。そして、修理する道を適切に選んだ時の「採算がとれる最低限の時給」の最小値を計算することにしました。「採算がとれる最低限の時給」とは、「道を修理するためにかかる時間の合計」×「時給」が「道を修理するためにかかる費用の合計」と等しくなる時の「時給」の金額の値を指します。
必ずしも全ての道を修理する必要はないことや、村をひと繋がりにするために必要のない道を修理しても良いことに注意して下さい。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 T_1 A_2 B_2 C_2 T_2 : A_M B_M C_M T_M
-
1 行目には、村の個数を表した整数 N (2 ≦ N ≦ 10^4) と、道の本数を表した整数 M (1 ≦ M ≦ 10^4) が空白区切りで与えられる。
-
続く M 行には、道の情報が与えられる。このうちの i 行目には 4 つの整数 A_i (0 ≦ A_i ≦ N-1), B_i (0 ≦ B_i ≦ N-1), C_i (1 ≦ C_i ≦ 10^6), T_i (1 ≦ T_i ≦ 10^6) が空白区切りで書かれており、これは 村 A_i と村 B_i を繋ぐ道があり、この道を修理するために費用が C_i、時間が T_i かかることを表している。
また、道の情報に関して以下の条件が成り立つとして良い。
- 全ての i について、A_i \neq B_i
- 全ての i, j (i \neq j) について、「A_i \neq A_j または B_i \neq B_j」かつ「A_i \neq B_j または B_i \neq A_j」
部分点
この問題には部分点が設定されている。
- M ≦ 16 を満たすテストケースすべてに正解した場合は 20 点が与えられる。
出力
「採算がとれる最低限の時給」の最小値を 1 行に出力せよ。
出力は絶対誤差が 10^{-2} 以下であれば許容される。
なお、出力の末尾には改行をいれること。
入力例1
3 2 0 1 5 3 1 2 5 2
出力例1
2
このケースでは、町をひと繋がりにするためには全ての道を修理しなければなりません。全ての道を修理するためにかかる費用の合計が 10 で時間の合計が 5 であるため、採算がとれる最低限の時給は 2 となります。
誤差は 10^{-2} まで許容されるため、2.01 や 1.99 などと出力しても正解となります。
入力例2
3 3 0 1 1 1 1 2 3 1 2 0 2 1
出力例2
1.500
このケースでは、1 つ目の道と 3 つ目の道を修理するときに「採算がとれる最低限の時給」が 1.5 となり、最小となります。
入力例3
4 4 0 1 1 1 1 2 1 1 2 0 1 1 0 3 5 3
出力例3
1.3333333
このケースでは、全ての道を修理するときに「採算がとれる最低限の時給」が 1.333... となり、最小となります。