A - 週末
高橋君は、週末が大好きです。高橋君は英語のデジタルカレンダーを使っているのですが、高橋君は英語の曜日を読むことができません。
カレンダーに表示されている曜日が与えられるので、あと何日で週末かを計算するプログラムを作成してください。
入力は以下の形式で標準入力から与えられる。
週末までの日数を出力せよ。なお、週末とは、土曜日および日曜日のことを表す。
もし、すでに週末であれば、 0 と出力すること。
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
カレンダーに表示されている曜日が与えられるので、あと何日で週末かを計算するプログラムを作成してください。
入力
day
- 1 行目に day が与えられる。
- day は曜日を表す文字列で
Sunday(日曜日)、Monday(月曜日)、Tuesday(火曜日)、Wednesday(水曜日)、Thursday(木曜日)、Friday(金曜日)、Saturday(土曜日) のいずれかである。
出力
もし、すでに週末であれば、 0 と出力すること。
出力は標準出力におこない、末尾には改行をいれること。
入力例 1
Monday
出力例 1
5
- 月曜日から土曜日までの日数は、 5 日です。
入力例 2
Saturday
出力例 2
0
- 土曜日は週末に含まれるので、 0 と出力します。
入力例 3
Sunday
出力例 3
0
- 日曜日は週末に含まれるので、 0 と出力します。
入力例 4
Wednesday
出力例 4
3
- 水曜日から土曜日までにかかる日数は、 3 日です。
B - アキレスと亀
高橋君は、カメが大好きです。高橋君は L メートル先にカメを見つけたので、このカメを追いかけて、捕まえようと思いました。
ですが、カメは高橋君が苦手です。カメは、高橋君から追いかけられ始めた瞬間、高橋君と反対の方向に逃げていきます。
高橋君の追いかける速度は秒間 v_a メートルで、カメの逃げる早さは秒間 v_b メートルです。
ここで高橋君はふと疑問に思いました。
高橋君が、今カメのいる場所までたどり着いた時、カメはさらに少し先に進んでいます。
そのカメがいる場所まで高橋君がたどり着くと、カメはその少し先にまた進んでいます。
これでは何度繰り返しても永遠にカメに追いつかないのではないでしょうか。
高橋君は、この事実を調査するため、この動作を N 回繰り返した時に、カメと高橋君の距離がどれだけ縮まっているかを調べたいです。
高橋君とカメの距離を出力するプログラムを作成してください。
なお、高橋君はカメがいるところまでまっすぐ最短距離を進みます。
また、動作を開始した時点でカメがいたところまで高橋君が移動することを 1 回の移動として数えるので、それぞれの移動にかかる時間が異なることに気をつけてください。
入力は以下の形式で標準入力から与えられる。
カメのいる場所に高橋君が移動する動作を N 回行った後の、高橋君とカメの距離を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
ですが、カメは高橋君が苦手です。カメは、高橋君から追いかけられ始めた瞬間、高橋君と反対の方向に逃げていきます。
高橋君の追いかける速度は秒間 v_a メートルで、カメの逃げる早さは秒間 v_b メートルです。
ここで高橋君はふと疑問に思いました。
高橋君が、今カメのいる場所までたどり着いた時、カメはさらに少し先に進んでいます。
そのカメがいる場所まで高橋君がたどり着くと、カメはその少し先にまた進んでいます。
これでは何度繰り返しても永遠にカメに追いつかないのではないでしょうか。
高橋君は、この事実を調査するため、この動作を N 回繰り返した時に、カメと高橋君の距離がどれだけ縮まっているかを調べたいです。
高橋君とカメの距離を出力するプログラムを作成してください。
なお、高橋君はカメがいるところまでまっすぐ最短距離を進みます。
また、動作を開始した時点でカメがいたところまで高橋君が移動することを 1 回の移動として数えるので、それぞれの移動にかかる時間が異なることに気をつけてください。
入力
N v_a v_b L
- 1 行目に、高橋君の移動回数を表す整数 N(1≦N≦100) 、高橋君の秒間移動距離を表す整数 v_a(1≦v_a≦100)、カメの秒間移動距離を表す整数 v_b(1≦v_b＜v_a)、高橋君とカメの最初の距離を表す整数 L(1≦L≦100) が、空白区切りで与えられる。
出力
出力は標準出力におこない、末尾には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
入力例 1
3 2 1 16
出力例 1
2
- 1 回目の移動で、高橋君が距離 16 メートルを 8 秒で移動します。この時、カメは 8 メートル先に進んでいます。
- 2 回目の移動で、高橋君が距離 8 メートルを 4 秒で移動します。この時、カメは 4 メートル先に進んでいます。
- 3 回目の移動で、高橋君が距離 4 メートルを 2 秒で移動します。この時、カメは 2 メートル先に進んでいます。
入力例 2
100 100 1 100
出力例 2
0
- 高橋君が秒速 100 メートルで走っても、カメに追いつくことはできませんが、距離は 0 に限りなく近くなります。
- 指数表記での出力ですと、不正解となることがありますので、注意してください。
入力例 3
80 50 49 72
出力例 3
14.302717205907
C - 五目並べチェッカー
高橋君は、五目並べが大好きです。
五目並べとは、 19 × 19 の碁盤の上に交互に碁石を 1 つずつ並べ、 5 つ以上の碁石が縦・横・ななめに並べたプレーヤーが勝ちとなってゲームが終了する、というルールのゲームです。
ゲームは必ず黒のプレーヤーから始めるものとします。
高橋君は、友達の青木君と五目並べをしていたのですが、うっかり居眠りをしてしまいました。
高橋君は寝ている間に青木君が不正をしたのではないかと疑っているので、盤面から五目並べの状態として異常なところがないかを探したいです。
五目並べの状態として、正常であるかどうか判定するプログラムを作ってください。
ここでの異常な状態とは、
入力は以下の形式で標準入力から与えられる。
盤面が正常な状態であれば、
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
五目並べとは、 19 × 19 の碁盤の上に交互に碁石を 1 つずつ並べ、 5 つ以上の碁石が縦・横・ななめに並べたプレーヤーが勝ちとなってゲームが終了する、というルールのゲームです。
ゲームは必ず黒のプレーヤーから始めるものとします。
高橋君は、友達の青木君と五目並べをしていたのですが、うっかり居眠りをしてしまいました。
高橋君は寝ている間に青木君が不正をしたのではないかと疑っているので、盤面から五目並べの状態として異常なところがないかを探したいです。
五目並べの状態として、正常であるかどうか判定するプログラムを作ってください。
ここでの異常な状態とは、
- どちらかのプレーヤーの勝利条件を満たしているのに、もう片方のプレーヤーがさらに碁石を置いている。
- お互いが置いた個数がありえない状態になっている。
入力
b_{1,1} b_{2,1} ‥‥ b_{19,1}
b_{1,2} b_{2,2} ‥‥ b_{19,2}
:
:
b_{1,19} b_{2,19} ‥‥ b_{19,19}
- 入力は 19 行与えられる。
- i(1≦i≦19) 行目の j(1≦j≦19) 文字目には、盤面の縦 i 番目、横 j 番目のマスの情報を表す文字 b_{i,j} が与えられる。
- b_{i,j} は、
o、x、.の 3 種類のいずれかの文字である。oは、黒石が置かれていることを表す。xは、白石が置かれていることを表す。.は、何も置かれていないことを表す。
出力
YES、そうでなければ NO と出力しなさい。 出力は標準出力におこない、末尾には改行をいれること。
入力例 1
................... ................... ................... ................... ....x......o....... ................... ................... .......o....o...... ................... ........x.......... ..............o.... ................... .......x........... ................... ................... ................... ................... ................... ...................
出力例 1
YES
- 黒が 4 手、白が 3 手打った状態です。
- （記述に誤りがありましたので、修正しました。）
入力例 2
................... ................... ................... ................... ....x......o....... ................... ................... .......o....o...... ................... ........x.......... ..............o.... ................... .......x........... ................... ................... .........o......... ................... ................... ...................
出力例 2
NO
- 黒が 5 手、白が 3 手打った状態です。
- 黒が 1 手多く打ってしまっているので、異常な状態です。
入力例 3
................... ................... ................... ................... ................... ................... ................... ................... ........ooooo...... .........xxxx...... ........x.......... ................... ................... ................... ................... ................... ................... ................... ...................
出力例 3
NO
- 黒が 5 手、白が 5 手打った状態です。
- 片方が勝利条件を満たしていればゲームは終了しているので、黒が勝利条件を満たしているのは異常な状態です。
- （記述に間違いがありましたので、訂正しました。）
入力例 4
................... ................... ................... ................... ................... ................... ................... ................... ........ooooo...... .........xxxx...... ................... ................... ................... ................... ................... ................... ................... ................... ...................
出力例 4
YES
- 黒が 5 手、白が 4 手打った状態です。
- 黒が 5 つ並べて勝利した状態となり、正常です。
入力例 5
................... ................... ................... ................... ................... ................... ................... ................... .........x......... ......oooooo....... ........xxxx....... ................... ................... ................... ................... ................... ................... ................... ...................
出力例 5
YES
- 黒石が 6 つ並んでいますが、正常です。
- 例えば黒石が 2 つ並んでおり、1 マス空いてさらに 3 つ並んでいる状態で、空いている真ん中のマスに黒石を置いた場合このような形になります。
入力例 6
................... ................... ................... ................... ................... ................... ........x.......... ........x....x..... ...........x....... ...oooooooooo...... ................... ......x......x..... ....x......x....... .........x......... ................... ................... ................... ................... ...................
出力例 6
NO
- 黒が 10 手、白が 9 手打った状態です。
- 黒石を 10 個並べる前に、黒が勝利してゲームが終了していないとおかしいので、異常な状態です。
入力例 7
................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ...................
出力例 7
YES
- 黒が高橋君で、一手も打たないうちに居眠りしてしまった場合も、正常な状態です。
D - Don't worry. Be Together
N 人の人間が、二次元平面上の格子点にいます。
各ターンごとに、各自が上下左右いずれかの方向へちょうど 1 だけ進みます。
これを繰り返し、T ターンの終了時に全員が同時に原点 (0,0) へ集まるようにしたいです。
その時の各自の進み方の組み合わせが何通りあるかを、 modulo で割った余りを出力してください。
どのようにしても全員が同時に原点に集まることができない場合は、 0 を出力してください。
入力は以下の形式で標準入力から与えられる。
テストデータには以下の 3 種類のテストデータセットのいずれかに含まれており、それぞれのデータセットに含まれているテストデータは、以下に示すように与えられる整数 modulo,\ x_i,\ y_i の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
ちょうど T ターン後に全員が原点に集まるための進み方が何通りあるかを、moduloで割った余りを出力せよ。
どのようにしても全員が同時に原点に集まることができない場合は、0 を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
各ターンごとに、各自が上下左右いずれかの方向へちょうど 1 だけ進みます。
これを繰り返し、T ターンの終了時に全員が同時に原点 (0,0) へ集まるようにしたいです。
その時の各自の進み方の組み合わせが何通りあるかを、 modulo で割った余りを出力してください。
どのようにしても全員が同時に原点に集まることができない場合は、 0 を出力してください。
入力
N T modulo x_1 y_1 x_2 y_2 : : x_N y_N
- 1 行目に、人間の数を表す整数 N(1≦N≦100,000) 、移動ターン数を表す整数 T(1≦T≦100,000) 、正整数 modulo が、空白区切りで与えられる。
- 2 行目から N 行間における i+1(1≦i≦N) 行目には、i 番目の人がいる座標を表す整数 x_i,\ y_i が、空白区切りで与えられる。
部分点
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
- part1 ( 40 点) : modulo=1,000,000,007、-1,000,000≦x_i,\ y_i≦1,000,000
- part2 ( 30 点) : 1≦modulo≦1,000,000,007、-100≦x_i,\ y_i≦100
- part3 ( 30 点) : 1≦modulo≦1,000,000,007、-1,000,000≦x_i,\ y_i≦1,000,000
出力
どのようにしても全員が同時に原点に集まることができない場合は、0 を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。
入力例 1
2 2 1000000007 1 1 -1 -1
出力例 1
4
- x 座標が正の方向を右、y 座標が正の方向を上とします。
- 2 ターン目に二人が原点に辿り着く方法は、以下の 4 通りとなります。
- 1人目が、下・右の順に移動し、2人目が、上・左の順に移動する。
- 1人目が、下・右の順に移動し、2人目が、左・上の順に移動する。
- 1人目が、右・下の順に移動し、2人目が、上・左の順に移動する。
- 1人目が、右・下の順に移動し、2人目が、左・上の順に移動する。
入力例 2
4 4 1000000007 0 4 4 0 -4 0 0 -4
出力例 2
1
- それぞれ、まっすぐ原点に向かって進むパターン以外存在しないので、答えは 1 通りとなります。
入力例 3
1 6 10 0 0
出力例 3
0
- 6 ターンで原点から原点に戻ってくる方法は 400 通りあるので、 10 で割った余りの 0 を出力します。
入力例 4
3 7 12345 2 3 0 1 -2 -1
出力例 4
11415