Time Limit: 2 sec / Memory Limit: 256 MB
問題文
クイズです。
- 第 1 問: あなたが今参加しているこのコンテストの略称は何でしょう? アルファベット大文字 3 文字で答えてください。
- 第 2 問: あなたが今参加しているこのコンテストなどを運営しているAtCoder株式会社の代表取締役社長は誰でしょう? アルファベット小文字 8 文字のハンドルネームで答えてください。
標準入力から整数 1 または 2 が与えられます。 1 が入力された場合は第 1 問の答えを、 2 の場合は第 2 問の答えを出力してください。
なお、クイズの答えに関してはこの問題ページ内に記載があります。
入力
入力は以下の形式で標準入力から与えられる。
Q
- 1 行目に、答えるべき問題を指定する 1 個の整数 Q (Q = 1 または Q = 2) が与えられる。
出力
標準出力に、 Q = 1 であれば第 1 問の答えを、 Q = 2 であれば第 2 問の答えを出力せよ。アルファベットの大文字と小文字は区別される。
末尾の改行を忘れないこと。
入力例1
1
出力例1
ABC
入力例2
2
出力例2
chokudai
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
2 つの正整数 A, B が与えられます。 A の十進表記の右に B の十進表記(先頭に 0 を付けない)を連結して得られる整数を 2 倍したものを出力してください。
入力
入力は以下の形式で標準入力から与えられる。
A B
- 1 行目に、 2 個の整数 A, B (1 ≦ A, B ≦ 999) がスペース区切りで与えられる。
出力
標準出力に指示された値を出力せよ。
末尾の改行を忘れないこと。
入力例1
1 23
出力例1
246
123 × 2 = 246 となります。
入力例2
999 999
出力例2
1999998
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
正方形のマスが縦 H 行、横 W 列に並んでいます。各マスは白または黒で塗られており、白マスのうち 2 つがそれぞれスタート地点とゴール地点として指定されています。
高橋君はスタート地点から出発して T 秒以内にゴール地点に到着したいです。高橋君は、各マスから上下左右に隣接する別のマスに移動することができます。このとき、移動先が白マスであれば 1 秒、黒マスであれば x 秒の時間がかかります(移動前のマスの色は移動時間に影響しません)。ここで、 x の値は高橋君がスタート地点から出発する前にあなたに選んでもらいます。 x の値は正整数でなければならず、高橋君の出発後に値を変更することはできません。
高橋君が T 秒以内にゴール地点に到着することが可能であるような正整数 x の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
H W T s_{1,1}s_{1,2} .. s_{1,W} s_{2,1}s_{2,2} .. s_{2,W} : s_{H,1}s_{H,2} .. s_{H,W}
- 1 行目には、 3 個の整数 H, W, T (2 ≦ H, W ≦ 10, 2 ≦ T ≦ 10^9) が与えられる。これらはそれぞれ、マスの行数と列数、および高橋君の目標時間を表す。
- 2 行目から H + 1 行目には、各マスの情報が与えられる。 i + 1 行目の j 文字目 s_{i,j} が i 行 j 列目のマスに対応する。各文字の意味は以下の通り:
.
: スタート地点にもゴール地点にも指定されていない白マスS
: スタート地点として指定された白マスG
: ゴール地点として指定された白マス#
: 黒マス
S
およびG
はそれぞれちょうど 1 個ずつ出現する。また、入力では求める最大値が存在することが保証される。すなわち、少なくとも 1 度は黒マスに移動しなければスタート地点から出発してゴール地点に到着できないこと、および x = 1 のとき T 秒以内にゴール地点に到着することが可能であることが保証される。
部分点
この問題には部分点が設定されている。
- 40 点分のテストケースは 2 ≦ H, W ≦ 3, 2 ≦ T ≦ 30 を満たす。
- 別の 30 点分のテストケースは 2 ≦ T ≦ 30 を満たす。
(※ 問題 D にも部分点が設定されています。そちらもご確認ください。)
出力
標準出力に、 高橋君が T 秒以内にゴール地点に到着することが可能であるような正整数 x の最大値を出力せよ。
末尾の改行を忘れないこと。
入力例1
2 3 10 S## .#G
出力例1
8
i 行 j 列目のマスを (i, j) で表します。 x = 8 のとき、 (1, 1) → (2, 1) → (2, 2) → (2, 3) と移動すると 1 + 8 + 1 = 10 秒でゴール地点に到着することができます。 x \geq 9 のとき、 10 秒以内にゴール地点に到着することはできません。
入力例2
3 4 7 S##G .##. ..#.
出力例2
3
スタート地点から右に直進すると 2x + 1 秒でゴール地点に到達できます。遠回りすることで黒マスへの移動回数を減らすことができますが、 x の値によってはかえって時間がかかってしまいます。
入力例3
4 4 1000000000 S### #### #### ###G
出力例3
199999999
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
2 つの正整数 a, b の最小公倍数 LCM(a, b) とは、 a の倍数であり、かつ b の倍数でもあるような正整数のうち最小のものをいいます。
2 つの正整数 N, K が与えられます。 1 以上 N 以下のすべての整数 i について LCM(i, K) を足しあわせたものを 1,000,000,007 で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K
- 1 行目に、 2 個の整数 N, K (1 ≦ N, K ≦ 109) がスペース区切りで与えられる。
部分点
この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 (100 点満点) と異なり 101 点満点であり、部分点が設定されている。
- 5 点分のテストケースは 1 ≦ N, K ≦ 100 を満たす。
- 別の 10 点分のテストケースは 1 ≦ N ≦ 104, 1 ≦ K ≦ 100 を満たす。
- さらに別の 85 点分のテストケースは 1 ≦ N ≦ 109, 1 ≦ K ≦ 100 を満たす。以上で合計 100 点となる。
出力
標準出力に、求める和を 1,000,000,007 で割った余りを出力せよ。
末尾の改行を忘れないこと。
入力例1
4 2
出力例1
14
LCM(1, 2) + LCM(2, 2) + LCM(3, 2) + LCM(4, 2) = 2 + 2 + 6 + 4 = 14 となります。
入力例2
10000 100
出力例2
865504986
入力例3
1000000000 90
出力例3
50001213
入力例4
1000000000 999999900
出力例4
231285006