Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高梁空港には、周長 L の円形の動く歩道があり、その床面は 1 秒間に距離 X 進む速度で時計回りに動いています。 動く歩道のある円周上の点の位置は、その中で最も北にある点から時計回りに測った距離 ( 0 以上 L 未満) であらわされます。 動く歩道の外周の位置 D の点には出口があり、そこから動く歩道の外に出ることができるようになっています。 それ以外の外周と内周には手すりがあるため、高橋君は出口以外の場所から外に出ることはできません。
高橋君は動く歩道の床面に対して 1 秒間に距離 Y 進む速度で時計回りまたは反時計回りに歩くことができ、動く歩道上の位置 S の点に乗っています。
高橋君が出口にたどり着くまでにかかる最小の時間を求めてください。
なお、出口の 1 箇所しかない動く歩道にわざわざ乗るような物好きな人は高橋君以外にはいないので、動く歩道を逆走しても誰にも迷惑をかけることはありません。
制約
- 1 ≦ L,X,Y ≦ 10^9, 0 ≦ S,D ≦ L-1
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
L X Y S D
出力
高橋君が出口にたどり着くまでにかかる最小の時間を 1 行に出力せよ。絶対誤差あるいは相対誤差が 10^{-6} 以下のとき正答と認められる。
出力の最後には改行を忘れないこと。
入力例1
6 2 3 1 5
出力例1
0.8000000000
時計回りに歩き続けると 0.8 秒で出口にたどり着くことができます。
入力例2
6 2 10 1 5
出力例2
0.2500000000
反時計回りに歩き続けると 0.25 秒で出口にたどり着くことができます。
入力例3
6 3 1 5 3
出力例3
1.0000000000
入力例4
10 7 7 6 0
出力例4
0.2857142857
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はタカハシマン関数という関数に興味を持ちました。高橋君は T(334) ( T はタカハシマン関数を表す)を計算したいと思いましたが、それは現代のコンピュータでは P 年がかかるため、とても難しいということが分かりました。
半ば計算をあきらめかけていた高橋君でしたが、世の中にはムーアの法則という法則があることを知りました。 ムーアの法則によると、コンピュータの速度は 1.5 年ごとに 2 倍になる速度で、指数関数的に増大することが分かりました。
より正確には、x 年後にはコンピュータの速度は現代の 2^{x/1.5} 倍になります。
高橋君は適切なタイミングで計算を始めることで、T(334) の計算をできるだけ早く終わらせたいと思いました。 もちろん計算中にコンピュータを変えることはできないので、計算を終えるまでの時間は (計算を始めるまでの時間)+(計算を始めた時点のコンピュータで T(334) を計算するのにかかる時間) であらわされます。
計算が終わるまでの最短の時間を求めてください。
制約
- 0 < P ≦ 10^{18}
- P は実数で、小数点以下第 4 位まで与えられる。
入力
入力は以下の形式で標準入力から与えられる。
P
出力
計算が終わるまでにかかる最小の時間を 1 行に出力せよ。絶対誤差あるいは相対誤差が 10^{-8} 以下のとき正答と認められる。
出力の最後には改行を忘れないこと。
入力例1
3.0000
出力例1
2.8708930019
入力例2
0.0400
出力例2
0.0400000000
入力例3
1000000000000000000.0000
出力例3
90.1855078128
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の家にはタイヤが N 個と木が N 本あります。高橋君は、これらを一つずつ組み合わせて鯛焼きを N 個作ることにしました。
タイヤと木の組には相性があり、相性のいいタイヤと木の組み合わせでのみおいしい鯛焼きを作ることができます。 高橋君はおいしい鯛焼きしか食べないので、作る N 個の鯛焼きすべてが、相性のいいタイヤと木の組み合わせでできている必要があります。
高橋君はこの条件を満たすように鯛焼きを作る方法が何通りあるのかが気になりましたが、これはとても数えられそうにないことに気付きました。
そこで高橋君は、その方法の数の偶奇だけを求めることにしました。
高橋君は、すべてのタイヤと木のペアについて、そのペアの相性がいいかどうかを表あらわす表 (S_{ij}) を持っています。この表は N 行 N 列からなり、i 行 j 列の要素が 1 のとき i 番目のタイヤと j 番目の木の相性がいいことを、 0 のとき悪いことを表します。 高橋君に代わって、すべての鯛焼きをおいしくするような組み合わせ方の数の偶奇を求めてください。 ただし、 2 つの組み合わせ方が異なるとは、あるタイヤが存在し、そのタイヤが別の木と組み合わせられて鯛焼きが作られていることを指します。
制約
- 1 ≦ N ≦ 200
- S_{ij}=0 もしくは S_{ij}=1 (1 ≦ i,j ≦ N)
入力
入力は以下の形式で標準入力から与えられる。
N
S_{11}S_{12}..S_{1N}
:
S_{N1}S_{N2}..S_{NN}
出力
すべての鯛焼きをおいしくするような組み合わせの個数が偶数なら "Even" 、奇数なら "Odd" を出力せよ。
出力の最後には改行を忘れないこと。
入力例1
3 110 101 011
出力例1
Even
2 通りの組み合わせ方があります。
入力例2
3 110 111 011
出力例2
Odd
3 通りの組み合わせ方があります。
入力例3
2 00 00
出力例3
Even
0 通りの組み合わせ方があります。
入力例4
12 000000100000 011111111111 000000100000 000111111100 100100000100 100111111100 100100000100 100111111100 100100000100 100111111100 100000000000 111111111111
出力例4
Even
Time Limit: 5 sec / Memory Limit: 512 MB
問題文
高橋君は、毎年誕生日にお母さんから数列をもらっています。 高橋君はバブルソートの交換回数を求めるのが好きなので、毎年、お母さんからもらった数列のバブルソートの交換回数を求めるのを楽しんできました。
しかし今年のお母さんは一味違います。なんと、高橋君がバブルソートの交換回数を求めるのをより一層楽しめるように、とても長い数列を圧縮したものを高橋君に渡したのです。
長さ 10^7 の数列のバブルソートの交換回数なら目視で 1 秒とかからずに求められる高橋君でも、この数列には歯が立ちませんでした。
あなたの仕事は、高橋君に代わってこの数列のバブルソートの交換回数を 10^9+7 で割ったあまり求めることです。
ただし、バブルソートとは、以下の擬似コードで与えられるアルゴリズムです。
input: a[1],...,a[N]
for i=1 to N-1
{
for j=1 to N-i
{
if a[j]>a[j+1] swap(a[j],a[j+1])
}
}
バブルソートの交換回数とは、上の疑似コードでswapが呼ばれる回数です。
また、圧縮された列からもとの数列を得る方法は、以下の通りです。
- 最初、ポインタは圧縮列の最初の項を指しており、スタックは空である。以下の操作をポインタの位置が圧縮列からはみ出すまで繰り返す。最終的にスタックに残ったひとつの数列が、目的の数列である。
- ポインタの指す値が正なら、スタックにその値の項ひとつからなる数列を積み、ポインタを一つ進める。
- ポインタの指す値が 0 なら、スタックの上から 1 番目と 2 番目の数列を取り出し、後者の後ろに前者をつなげた数列をスタックに積み、ポインタを一つ進める。
- ポインタの指す値が負なら、スタックの一番上の数列を取り出し、それを |ポインタの指す値| 回繰り返したものをスタックに積み、ポインタを一つ進める。
例えば、列
1 2 3 0 -4 5 0 0 -2は数列
1 2 3 2 3 2 3 2 3 5 1 2 3 2 3 2 3 2 3 5を表します。
制約
- N > 0
- -10^5 ≦ A_i ≦ 10^5(1 ≦ i ≦ N)
- A_i ≠ 0 なる i の個数は 10^5 を超えない。
- 与えられる圧縮列からは、上述の方法によって元の数列が復元できることが保障される。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 ... A_N
部分点
この問題には部分点が設定されている。
- 圧縮列の 0 でない要素の個数が 2000 を超えないデータセットに正解した場合、部分点として50点が与えられる。
出力
圧縮列が表す数列のバブルソートの交換回数を 10^9+7 で割った余りを出力せよ。
出力の最後には改行を忘れないこと。
入力例1
9 1 2 3 0 -4 5 0 0 -2
出力例1
45
入力例2
22 12 35 -901 0 43 73 0 -18 2 6 0 -9 428 0 0 0 -23 8 0 -66 2 0
出力例2
509114582