Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は太りやすく痩せやすい体質です。そこで彼は N 日間の体重の変化量を記録してみました。
1 日目の高橋くんの体重は W キログラムでした。 i 日目 (2≦i≦N) の体重の変化量は A_i キログラムでした(A_i は負になり得ます)。 つまり i-1 日目の体重を X キログラムとすると、 i 日目の体重は X + A_i キログラムだったということです。
ところで、高橋君の個人的な価値観では、体重が S キログラム以上 T キログラム以下の体型が「ベストボディー」だと考えています。
体重を記録した N 日間のうち、高橋君がベストボディーであった日数を求めてください。
入力
入力は以下の形式で標準入力から与えられる
N S T W A_2 A_3 : A_N
- 1 行目には高橋君が体重を記録した日数を表す整数 N(2 ≦ N ≦ 1,000) 、ベストボディーの基準となる値 S, T(1 ≦ S ≦ T ≦ 10^5) が空白区切りで与えられる。
- 2 行目には 1 日目の高橋君の体重を表す整数 W(1 ≦ W ≦ 10^5) が与えられる。
- 3 行目からの N-1 行のうち i 行目には i+1 日目の体重の変化量を表す整数 A_{i+1}(-10^5 ≦ A_{i+1} ≦ 10^5) が与えられる。
- 高橋君の体重が 0 キログラム以下になることはない。
出力
高橋君がベストボディーであった日数を 1 行で出力せよ。出力の末尾にも改行を入れること。
入力例1
5 60 70 50 10 10 10 10
出力例1
2
高橋君の体重を 1 日目から順に書き出すと 50, 60, 70, 80, 90 になります。 よって2 日目と 3 日目にのみ高橋君はベストボディーだったことになります。
入力例2
5 50 100 120 -10 -20 -30 70
出力例2
2
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はマルハナバチ(Bumblebee)という種類のミツバチです。
今日も花の蜜を求めて異なる N 個の花を訪れました。
高橋君が i 番目に訪れた花の種類は A_i です。
i 番目の花は、i > j かつ i 番目の花の種類と j 番目の花の種類が同じになるような j が存在すれば受粉します。
高橋君が訪れた N 個の花の種類の情報が与えられるので、そのうちいくつの花が受粉したか求めてください。
なお、高橋君以外による受粉や自家受粉を考える必要はありません。
入力
入力は以下の形式で標準入力から与えられる
N A_1 A_2 : A_N
- 1 行目には高橋君が訪れた花の個数を表す整数 N(1 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行のうち i 行目には i 番目に高橋君が訪れた花の種類を表す整数 A_i (1 ≦ A_i ≦ 10^5) が与えられる。
出力
受粉した花の個数を 1 行で出力せよ。出力の末尾にも改行を入れること。
入力例1
5 1 2 3 2 1
出力例1
2
4 番目と 5 番目の花が受粉します。
入力例2
11 3 1 4 1 5 9 2 6 5 3 5
出力例2
4
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の住む街には N 個の家と M 個の道があります。 家は 1 ～ N の整数によって番号付けされています。 高橋君は家 1 に住んでいます。 道も 1 ～ M の整数によって番号付けされています。 i 番目の道は家 u_i と 家 v_i を双方向につなぐ長さ l_i メートルの道です。
高橋君は街のどこかの家に居るという「幸せの青い鳥」を探しています。 実は、「幸せの青い鳥」は高橋くんの家にいて、高橋君もそのことを知っています。 しかし、形だけでも探す旅に出ないと盛り上がりに欠けて面白くないので、仕方なく旅の計画をたてることにしました。
高橋君は自分の家から開始して、同じ道を二度以上通らないようにいくつかの家に訪れ、最後に自分の家に戻ってくる、という旅の計画をたてる予定です。 このとき盛り上がりを作るために、旅の途中で自分の家以外の家を少なくとも 1 軒訪れる予定です。 高橋君はこの茶番をできるだけ早く終わらせたいので、通る道の長さの総和が最も小さくなるような計画が最適だと考えています。
高橋君の住む街の家と道の情報が与えられるので、高橋君が上の条件のもとで最適な計画をたてることができるかどうかを求めてください。 もし最適な計画をたてることができるならば、そのとき通る道の長さの総和を求めてください。
入力
入力は以下の形式で標準入力から与えられる
N M u_1 v_1 l_1 u_2 v_2 l_2 : u_M v_M l_M
- 1 行目には高橋君の住む街にある家の個数 N(3 ≦ N ≦ 300) と 道の本数 M(3 ≦ M ≦ N(N-1)/2) が空白区切りで与えられる。
- 2 行目からの M 行のうち i 行目には i 番目の道路が結ぶ家の番号 u_i, v_i(1 ≦ u_i ＜ v_i ≦ N) とその長さを表す整数 l_i(1 ≦ l_i ≦ 10^5) が空白区切りで与えられる。
- i ≠ j ならば u_i ≠ u_j または v_i ≠ v_j の少なくとも一方が成り立つ。
出力
最適な計画をたてることができないならば -1 を、できるならばそのとき通る道の長さの総和を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
5 7 1 2 2 1 4 1 2 3 7 1 5 12 3 5 2 2 5 3 3 4 5
出力例1
13
家と道の様子は以下のようになります
1, 2, 5, 3, 4, 1 という順番に訪れる計画が最適です。 1, 2, 1 という順番に訪れる計画は 1 番目の道を 2 回通っているので条件を満たしていません。
入力例2
5 4 1 2 1 1 3 1 1 4 1 1 5 1
出力例2
-1
同じ道を 2 度以上通らない旅の計画をたてることはできません。よって -1 を出力します。
入力例3
10 12 1 4 3 1 9 1 2 5 4 2 6 1 3 7 5 3 10 9 4 7 2 5 6 6 5 8 5 6 8 3 7 9 5 8 10 8
出力例3
11
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
宇宙はビッグバンによって誕生して以来、膨張し続けていることが知られています。
天文学者である高橋君はその宇宙の膨張の速度を計測することにしました。
高橋君はある 2 つの日について、同じ N 個の星の位置を観測しました。星の位置は座標平面上の点として記録されます。つまり各日の観測結果は座標平面上の N 個の点からなる点集合になります。
2 回の観測の結果を見比べてみると、1 回目の観測結果である点集合に対して以下の 3 つの操作を順に実行すると 2 回目の観測結果である点集合に一致することがわかりました。
- 同じ向きに同じ距離だけ平行移動する。
- 原点を中心に同じ角度だけ回転する。
- 原点を中心に P 倍 (1 ≦ P) に相似拡大する。つまり点 (a, b) を点 (a×P, b×P) に移すという操作をすべての点に実行する。
ここで P の値がわかれば膨張速度を求めることができそうです。
いざ P を求めようとした高橋君でしたが、うっかりどの点がどの星に対応するのか記したデータをなくしてしまいました。
そこで高橋君は優秀なプログラマーであるあなたに助けを借りることにしました。
1 回目と 2 回目の観測結果が与えられるので P を求めてください。
入力
入力は以下の形式で標準入力から与えられる
N Ax_1 Ay_1 Ax_2 Ay_2 : Ax_N Ay_N Bx_1 By_1 Bx_2 By_2 : Bx_N By_N
- 1 行目には高橋君が観測した星の個数 N (2 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行のうち i 行目には 1 回目に観測された i 番目の星の位置の x 座標と y 座標の値を表す 2 つの整数 Ax_i, Ay_i (-15,000 ≦Ax_i, Ay_i ≦ 15,000) が空白区切りで与えられる。
- N+2 行目からの N 行のうち i 行目には 2 回目に観測された i 番目の星の位置の x 座標と y 座標の値を表す 2 つの整数 Bx_i, By_i (-10^9 ≦Bx_i, By_i ≦ 10^9) が空白区切りで与えられる。
- 1 回目も 2 回目も、同じ点に複数の星が観測されることはない。
- 1 回目に観測された i 番目の星と 2 回目に観測された i 番目の星が同一の星とは限らない。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 3,000を満たすデータセットに正解した場合は 50 点が与えられる。
- 1 ≦ N ≦ 10^5を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。
出力
P の値を 1 行に出力せよ。 出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。出力の末尾にも改行を入れること。
入力例1
4 0 0 0 1 1 0 1 1 0 2 2 0 -2 0 0 -2
出力例1
2.8284271247
以下のように操作を実行すれば、 1 回目の観測結果の点集合が、 2 回目の観測結果の点集合に移されます。
- x 軸方向に -0.5、 y 軸方向に -0.5 平行移動させる。
- 原点を中心にして、45° 時計回りに回転させる。
- 原点を中心に 2√2 倍する。
よって P = 2√2 となります。
入力例2
6 3 4 1 3 4 3 2 2 0 1 2 0 5 5 -1 2 -1 -3 2 1 2 6 4 -3
出力例2
2.2360679775