Time Limit: 2 sec / Memory Limit: 256 MB
問題文
野球のAtCoderリーグのシーズンが終了しました。チーム高橋は A 試合中 B 回勝ち、チーム青木は C 試合中 D 回勝ちました。AtCoderリーグでは勝率の高い順に高い順位が与えられます。チーム高橋とチーム青木のどちらが勝率で勝っているか答えるプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
A B C D
- 1 行目には、4 つの整数 A, B, C, D (1 ≦ A, B, C, D ≦ 100) が与えられる。
- B ≦ A かつ D ≦ C を満たすことが保証される。
出力
チーム高橋の勝率がより高いときは TAKAHASHI、チーム青木の勝率がより高いときは AOKI、両チームの勝率が等しいときは DRAW と 1 行に出力せよ。出力の末尾にも改行をいれること。
入力例1
5 2 6 3
出力例1
AOKI
チーム高橋の勝率は 2 / 5 = 0.4、チーム青木の勝率は 3 / 6 = 0.5 なので、チーム青木の勝率がより高いです。また、試合数は両チームで異なることがあります。
入力例2
100 80 100 73
出力例2
TAKAHASHI
試合数が同じときは、勝ちの多いチームの勝率が高くなります。
入力例3
66 30 55 25
出力例3
DRAW
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
n 時 m 分のアナログ時計があります。短針と長針のなす角度のうち小さい方を度数法で求めてください。
入力
入力は以下の形式で標準入力から与えられる。
n m
- 1 行目には、アナログ時計の時刻を表す整数 n, m ( 0 ≦ n ≦ 23, 0 ≦ m ≦ 59 ) が空白区切りで書かれている。
出力
短針と長針のなす角度を 1 行目に出力せよ。絶対誤差または相対誤差が 10^{-4} 以下であれば許容される。
末尾の改行を忘れないこと。
入力例1
15 0
出力例1
90
時計の短針と長針は以下の図のようになります。
赤の矢印が長針、オレンジの矢印が短針です。
入力例2
3 17
出力例2
3.5
時計の短針と長針は以下の図のようになります。
入力例3
0 0
出力例3
0
入力例4
6 0
出力例4
180
入力例5
23 59
出力例5
5.5000
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。
空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 空港Aから空港Bへの飛行機は N 本あり、i 番目の便は a_i 時に出発します。 空港Bから空港Aへの飛行機は M 本あり、j 番目の便は b_j 時に出発します。
ある飛行機には、出発する空港に出発する時刻以前にいれば乗ることができます。出発する時刻ちょうどに到着した場合も、すぐに飛行機に乗って出発できます。 高橋くんははじめ空港Aに 0 時にいます。 空港Aと空港Bの間を最大何往復できるか調べてください。
入力
入力は以下の形式で標準入力から与えられる。
N M X Y a_1 a_2 .. a_N b_1 b_2 .. b_M
- 1 行目には、空港Aから空港Bへの本数 N ( 1 ≦ N ≦ 10^5) 、空港Bから空港Aへの本数 M ( 1 ≦ M ≦ 10^5) が空白区切りで与えられる。
- 2 行目には、空港Aから空港Bへの飛行機にかかる時間 X ( 1 ≦ X ≦ 10^9) 、空港Bから空港Aへの飛行機にかかる時間 Y ( 1 ≦ Y ≦ 10^9) が空白区切りで与えられる。
- 3 行目には、N 個の空港Aから飛行機が出発する時刻を表す整数 a_i が空白を区切りとして与えられる。
- 4 行目には、M 個の空港Bから飛行機が出発する時刻を表す整数 b_j が空白を区切りとして与えられる。
- 1 ≦ a_i ≦ 10^9 (1 ≦ i ≦ N) であることが保証される。
- 1 ≦ b_j ≦ 10^9 (1 ≦ j ≦ M) であることが保証される。
- a_i < a_{i+1} (1 ≦ i ≦ N-1) であることが保証される。
- b_i < b_{j+1} (1 ≦ j ≦ M-1) であることが保証される。
出力
高橋くんが空港Aと空港Bの間を最大何往復できるかを 1 行に出力せよ。
末尾の改行を忘れないこと。
部分点
この問題には部分点が設定されている。
- 30 点分のテストケースにおいて、1 ≦ a_i ≦ 10^5, 1 ≦ b_j ≦ 10^5 ( 1 ≦ i ≦ N, 1 ≦ j ≦ M) を満たす。
入力例1
3 4 2 3 1 5 7 3 8 12 13
出力例1
2
1 時の空港Aを出発する飛行機に乗り、3 時に到着しますが、すぐに 3 時の空港Bを出発する飛行機に乗り、6 時に空港Aに到着します。 次に、7 時の空港Aを出発する飛行機に乗り、9 時に到着、12 時の空港Bを出発する飛行機に乗ると、合計 2 往復できます。3 往復する手段はありません。
入力例2
1 1 1 1 1 1
出力例2
0
空港Bに行くと空港Aに帰れないので、1 度も往復できません。
入力例3
6 7 5 3 1 7 12 19 20 26 4 9 15 23 24 31 33
出力例3
3
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 b_i と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語も知らないので、単語 i の意味を調べようとしたとき、単語 b_i の意味を調べようとします。ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。 しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。 ある単語 i を調べようとして、単語帳を参照し、単語 b_i を調べようとするまでを1ステップとします。
ミカミくんが単語 i を調べようとして、k ステップ経ったとき、ミカミくんはどの単語を調べようとしているでしょうか？
入出力
入力は以下の形式で標準入力から与えられる。
N a k b_1 b_2 … b_N
- 1 行目には、単語の数 N (2 ≦ N ≦ 10^5) とミカミくんが調べようとしている単語の番号 a (1 ≦ a ≦ N) がスペース区切りで与えられる。
- 2 行目には、ミカミくんが単語を調べるステップ数 k(1 ≦ k ≦ 10^{100000}) が与えられる。
- 3 行目には、各単語の説明を表す N 個の整数 b_1,...,b_N が空白区切りで与えられる。
- 1 ≦ b_i ≦ N かつ b_i ≠ i (1 ≦ i ≦ N) であることが保証される。
部分点
この問題には部分点が設定されている。
- k ≦ 10^{18} を満たすデータセットに正解した場合は 50 点が与えられる。
出力
ミカミくんが単語 a を調べようとしてから k ステップ経ったとき、調べようとしている単語の番号を 1 行に出力せよ。出力の末尾にも改行をいれること。
入力例1
6 4 5 2 3 1 2 6 5
出力例1
3
ミカミくんは、それぞれのステップで以下のように単語を調べます。
1 ステップ目で、単語 4 の意味を知るため、単語 2 を調べようとします。
2 ステップ目で、単語 2 の意味を知るため、単語 3 を調べようとします。
3 ステップ目で、単語 3 の意味を知るため、単語 1 を調べようとします。
4 ステップ目で、単語 1 の意味を知るため、単語 2 を調べようとします。
5 ステップ目で、単語 2 の意味を知るため、単語 3 を調べようとします。
よって、5 ステップ経ったとき、ミカミくんは単語 3 を調べようとしています。
入力例2
4 1 100000000000000000000 2 3 4 1
出力例2
1
k はたいへん大きくなることがあります。
入力例3
8 1 1 2 3 4 5 3 2 4 5
出力例3
2