AtCoder Beginner Contest 003

A - AtCoder社の給料

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

AtCoder社の社員である青木さんの給料は以下のように決められます。
ある月に、青木さんがタスクをこなした数を x とします。
この月の給料は、1 から x までの整数が 1 面ずつに書かれた x 面ダイスを振って出た目 {}\times{} 1 万円がもらえます。
ただし、このダイスは、どの面が出る確率も等しく 1/x です。
青木くんは、暮らしていくのに十分な給料が得られるかどうかが心配で、平均いくら程度給料がもらえるか調べたいです。
毎月、青木くんはちょうど N 個のタスクをこなすこととし、毎月の給料の平均値を求めるプログラムを書いてください。

A問題では、提出した結果、全てのテストに対する判定がWAまたはREになってしまった場合のみ、質問タブにて可能な限りのトラブルシューティングを受け付けます。

提出結果のURLを添えて、お気軽にご質問ください。

また、ページ下部、「よくある質問」も、併せてご活用ください。

入力

入力は以下の形式で標準入力から与えられる。

1 行目には、整数で、青木くんが毎月こなすタスクの数 N\ (4 ≦ N ≦ 100) が与えられる。

出力

青木くんがもらえる毎月の給料（単位は円）の平均値を 1 行で出力せよ。
絶対誤差、または、相対誤差が 10^{-6} 以下であれば許容される。
また、出力の末尾には改行を入れること。

入力例 1

出力例 1

1 万円から 6 万円がもらえる確率がそれぞれ 1/6 であるので、答えは

10000 \times (1/6) + 20000 \times (1/6) + 30000 \times (1/6) + 40000 \times (1/6) + 50000 \times (1/6) + 60000 \times (1/6) = 35000

となります。

入力例 2

出力例 2

B - AtCoderトランプ

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

AtCoder社では 1 人で行うトランプを使ったゲームが流行っています。
AtCoder社特製トランプでは、各カードにアルファベット小文字 1 文字（a～z）、または@の文字が書かれています。

ゲームは以下の手順で行います。

カードを同じ枚数ずつ 2 列に並べて文字列を 2 つ作ります。
@のカードは、それぞれa,t,c,o,d,e,rのどれかのカードと置き換えます。
2 つの列が指し示す文字列が同じであれば勝ち、同じでなければ負けです。

手順 1. で並べられた 2 つの列が指し示す2つの文字列与えられるので、適切に@を置き換えて、このゲームで勝つことができるかどうかを判定するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。

S
T

1 行目には、1 列目のトランプが表す文字列 S が与えられる。
2 行目には、2 列目のトランプが表す文字列 T が与えられる。

S、T ともにアルファベット小文字、および、@のみから構成されることが保証される。
S、T の文字数は等しく、1 文字以上、10文字以下であることが保証される。

出力

このゲームで勝つことが可能であればYou can winと、不可能であればYou will loseと（シングルクォーテーションを除いて）1 行で出力せよ。また、出力の末尾には改行を入れること。

入力例 1

ch@ku@ai
choku@@i

出力例 1

You can win

例えば、@をうまく置き換えることによって、両方ともchokudaiと一致させることが可能です。

入力例 2

aoki
@ok@

出力例 2

You will lose

4 文字目において、@ で i を置き換えることができないので、一致させることができません。

入力例 3

arc
abc

出力例 3

You will lose

2 文字目において、一致させることができません。

C - AtCoderプログラミング講座

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

AtCoder社では、優秀な競技プログラマーの講座動画を N 個配信しています。
初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。
高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)/2 に変化します。
高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。
講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。
ただし、高橋くんの初期レートは 0 です。

入力

入力は以下の形式で標準入力から与えられる。

N K
R_1 R_2 ... R_N

1 行目には、講座動画の数を表す整数 N\ (1 ≦ N ≦ 100) と高橋くんが見ることのできる動画の数を表す整数 K\ (1 ≦ K ≦ N) がスペース区切りで与えられる。
2 行目には、講座動画を配信している競技プログラマーのレートを表す整数 R_i\ (1 ≦ R_i ≦ 4,000) がスペース区切りで与えられる。

出力

高橋くんが達成できる最大レートを 1 行で出力せよ。
絶対誤差、または、相対誤差が 10^{-6} 以下であれば許容される。
また、出力の末尾には改行を入れること。

入力例 1

2 2
1000 1500

出力例 1

1000.000000

以下の方法が最適です。

まず、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1000)/2 = 500 になります。
次に、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 500 から (500+1500)/2 = 1000 になります。

しかし、例えば、以下の方法は最適ではありません。

まず、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1500)/2 = 750 になります。
次に、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 750 から (750+1000)/2 = 875 になります。

入力例 2

2 1
1000 1500

出力例 2

このケースでは高橋くんは 1 個の講座動画しか見ることができません。
レート 1500 の競技プログラマーの講座動画を見るのが最適です。

入力例 3

10 5
2604 2281 3204 2264 2200 2650 2229 2461 2439 2211

出力例 3

2820.031250000

D - AtCoder社の冬

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

AtCoder社の社員室は R \times C（R 行 C 列）の区画に区切られており、各区画には、社員のデスク、サーバーラックのどちらかがあるか、何もない空きスペースのどれかです。
AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。
しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。
そこで、

デスク、または、サーバーラックのある最も上の行のすぐ上、
デスク、または、サーバーラックのある最も下の行のすぐ下、
デスク、または、サーバーラックのある最も左の列のすぐ左、
デスク、または、サーバーラックのある最も右の列のすぐ右

の 4 辺で囲まれた区画を壁で囲みました。
すると壁で囲まれた領域は X \times Y（X 行 Y 列）の区画になりました。
また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。
もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを求めるプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。

R C
X Y
D L

1 行目には、AtCoder社の社員室の区画の行数、列数を表す整数 R,\ C\ (1 ≦ R, C ≦ 30) がスペース区切りで与えられる。
2 行目には、社員室の壁に囲まれた部分の区画の行数、列数を表す整数 X,\ Y\ (1 ≦ X ≦ R,\ 1 ≦ Y ≦ C) がスペース区切りで与えられる。
3 行目には、社員室にある社員のデスクの数、サーバーラックの数を表す整数 D,\ L\ (D, L ≧ 0,\ 1 ≦ D+L ≦ X \times Y) がスペース区切りで与えられる。

出力

社員室にどのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを 1 行で出力せよ。
また、出力の末尾には改行を入れること。

部分点

D+L = X \times Y の場合のテストケースに全て正解した場合、101 点満点中の 100 点が与えられる。
満点解法は非常に難しいので、部分点を確実に取ることから考えましょう。

入力例 1

3 2
2 2
2 2

出力例 1

このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。
以下の 12 通りの配置が考えられます。ここでDはデスク、Lはサーバーラック、.は何もないことを表します。

DD  DL  DL  LD  LD  LL  ..  ..  ..  ..  ..  ..
LL  DL  LD  DL  LD  DD  DD  DL  DL  LD  LD  LL
..  ..  ..  ..  ..  ..  LL  DL  LD  DL  LD  DD

入力例 2

4 5
3 1
3 0

出力例 2

このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。

入力例 3

23 18
15 13
100 95

出力例 3

364527243

このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。
社員室の配置パターンは 145180660592914517790287604376765671109248284280228061640640 通りで、これを 10^9+7 で割った余りである 364527243 を出力してください。

入力例 4

30 30
24 22
145 132

出力例 4

976668549

このケースは D+L=X \times Y を満たさないため、部分点のテストケースに含まれることはありません。
無理に正解しようとせず、余裕のある人だけ挑戦してみてください。