実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
DISCOの半導体を薄く作る技術により、SDカード 1 枚に入るチップの数が、A 枚から B 枚に増えました。 これまでの最大容量が C GBだった時、新しい最大容量を出力しなさい。
ここで、SDカードの最大容量とチップの数は比例関係にあります。すなわち、チップ 1 枚あたりの容量が x GBであったとき、SDカードに入っているチップの数が k 枚ならば、最大容量は kx GBとなります。
制約
- 1 ≦ A < B ≦ 1{,}000
- 1 ≦ C ≦ 1{,}000
- A, \, B, \, C はいずれも整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
答えを 1 行で出力せよ。絶対誤差、あるいは相対誤差が 10^{-6} 以下であれば許容される。
入力例 1
2 3 5
出力例 1
7.5000000000000000
入力例 2
90 120 100
出力例 2
133.3333333333333333
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
半径 R のウェーハを、以下の図のように等間隔で N 分割することにしました。この問題におけるウェーハとは、ある部品を作るのに使われる薄い円盤状の物体です。
ウェーハを N 分割するためのカットラインと呼ばれる線は N-1 本あり、上から 1, \, 2, \, 3, \, … \, , \, N-1 番のカットラインと呼ぶことにします。また、以下の図に示すような -M, \, … \, , \, -1, \, 0 番や N, \, N+1, \, … \, , \, N+M-1 番のカットラインも便宜上存在することにします。
ウェーハを N 分割するためには 1, \, 2, \, 3, \, … \, , \, N-1 番のカットラインに対して機械を使ってそれぞれ 2 回ずつカットと呼ばれる処理を行う必要があります。
カットはある機械を使って行われます。 1 から N+M-1 までの番号を指定して機械を稼働させると、2 枚の刃を使ってカットが並列に行われます。
i(1≦i≦N+M-1) 番を指定して機械を稼働させると 1 枚目の刃は i 番のカットラインのカットを行い、2 枚目の刃は i-M 番目のカットラインにカットを行います。このときのカット長は長い方のカットラインの長さで表されます。ここで、 0 番や N 番など i(1 ≦ i ≦ N-1) 番以外のカットラインの長さは 0 として構いません。
機械の動作の具体例を示します。N=6, \, M=3 のときに i=5 として機械を稼働させると、以下の図のように 2 番と 5 番のカットラインがカットされます。このときのカット長は 2 番のカットラインの方が 5 番のカットラインより長いため、2 番のカットラインの長さとなります。
1, \, 2, \, 3, \, … \, , \, N+M-1 と順番に指定して機械を稼働させることで、1, \, 2, \, 3, … \, , \, N -1 番のカットラインをそれぞれ 2 回カットが行われた状態にすることができます。このような手順でウェーハを N 分割するときのカット長の総和を出力してください。
制約
- 1 ≦ R ≦ 10^{5}
- 2 ≦ N ≦ 10^{5}
- 1 ≦ M ≦ N - 1
- R は整数
入力
入力は以下の形式で標準入力から与えられる。
R N M
出力
答えを 1 行で出力せよ。絶対誤差、あるいは相対誤差が 10^{-6} 以下であれば許容される。
入力例 1
1 4 1
出力例 1
7.4641016151377546
1 枚目の刃が上から 1, \, 2, \, 3, \, 4 番のカットラインを順番にカットするとき、それぞれのカット長は \sqrt{3}, \, 2, \, 2, \, \sqrt{3} となります。 0 番のカットラインの長さや、 4 番のカットラインの長さは 0 として扱ってよいことに注意してください。
入力例 2
40 37 5
出力例 2
2712.5411572217257024
入力例 3
100000 100000 1000
出力例 3
15907959408.6441142940893769
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
N 枚のカードが 1 列に並べられており、i(1 ≦ i ≦ N) 番目のカードには整数 A_i が書かれています。
この N 枚のカードを使ったロト 2 という宝くじがあります。 ロト 2 は 1 番から N 番までの番号から異なる 2 つの番号 i, \, j (i < j) を選び、選ばれた 2 つの番号のカードにそれぞれ書かれた値の積 A_i A_jが K の倍数となるとき当選するというルールで行われます。
A_iA_j が K の倍数となるような i と j の組合せ (i, \, j) を良い組合せと呼ぶことにします。良い組合せは何通りあるか求めなさい。
制約
- 1 ≦ N ≦ 200{,}000
- 1 ≦ A_i ≦ 10^{9} (1 ≦ i ≦ N)
- 1 ≦ K ≦ 10^{9}
- A_i, \, K はいずれも整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 … A_N
出力
良い組合せの総数を 1 行に出力せよ。
入力例 1
4 6 1 3 2 6
出力例 1
4
(1, \, 4), \, (2, \, 3), \, (2, \, 4), \, (3, \, 4) の 4 通りが良い組合せです。
入力例 2
5 1 1 2 3 1 2
出力例 2
10
どのように 2 つの番号を選んでも良い組合せになります。
入力例 3
12 60 38 19 180 222 560 1000 7 99 845 3600 12 90
出力例 3
33
実行時間制限: 3 sec / メモリ制限: 512 MB
配点 : 1200 点
問題文
N 個の都市と N-1 個の道からなる国があります。各都市には 1, \, 2, \, … \, , \, N と番号がついています。 i(1 ≦ i ≦ N-1) 番目の道は都市 A_i と都市 B_i を長さ C_i でつないでいます。 道は双方向に移動可能で、どの都市同士も何本かの道を通って互いに行き来することが可能です。
ある日、1≦i<j≦N を満たす 2 つの都市 i, \, j について都市 i と 都市 j を直接つなぐ道が存在しない場合、都市 i と 都市 j を直接つなぐ長さ X の道を追加する、という操作が行われました。
d(u, \, v) を都市 u から都市 v までの最短距離として、 1≦i<j≦N を満たす 2 つの都市 i, \, j について d(i, \, j) をそれぞれ求め、その総和を出力してください。
制約
- 2 ≦ N ≦ 10^{5}
- 1 ≦ A_i, \, B_i ≦ N(1 ≦ i ≦ N-1)
- 1 ≦ C_i ≦ 10^{5}(1 ≦ i ≦ N-1)
- 1 ≦ X ≦ 10^5
- 操作が行われる以前の時点において、どの 2 つの都市同士も何本かの道をたどって移動可能
- C_i, \, X はいずれも整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 C_{1} . . . A_{N-1} B_{N-1} C_{N-1}
出力
答えを 1 行に出力せよ。
入力例 1
6 3 1 2 2 2 3 3 4 1 4 6 4 10 5 4 8
出力例 1
51
以下の図は都市と道の関係を表します。青い実線は元々あった N-1 本の道を、黒い破線は操作により新たに追加された長さ 3 の道を表しています。
入力例 2
20 68 12 10 34 12 14 35 12 9 15 17 9 37 1 17 47 1 2 12 11 2 7 11 15 32 13 11 15 13 4 2 5 1 35 20 5 51 3 4 39 16 11 21 3 18 70 17 8 68 20 7 2 6 3 34 19 2 5
出力例 2
11278