Time Limit: 2 sec / Memory Limit: 64 MB
問題文
ある数学者は次の問題を考案したという。
- 1 つがいの兎は、産まれて 2 か月後から毎月 1 つがいずつの兎を産む。
- 兎が死ぬことはない。
- この条件のもとで、産まれたばかりの 1 つがいの兎は 1 年の間に何つがいの兎になるか?
※つがい:オスとメスの一組
この問題は上の問題をもとにした問題です。
今、 1 つがいの産まれたばかりの兎がいるとします。
上の問題の条件と同様に兎が増えるとすると、
n ヶ月後に何つがいの兎がいるでしょう?
このとき、 n ヶ月後ちょうどに産まれた兎のつがいも数に含めます。
入力
n
- 何ヶ月後かを表す整数 n (0 \leq n \leq 45) が 1 行で与えられる。
出力
なお、行の終端には改行が必要である。
入力例 1
0
出力例 1
1
入力例 2
5
出力例 2
8
-
2 ヶ月後に 1 つがい、
3 ヶ月後に 1 つがい、
4 ヶ月後に 2 つがい、 5 ヶ月後に 3 つがいが産まれ、
初めにいた 1 つがいと合わせて、合計 8 つがいとなる。
入力例 3
45
出力例 3
1836311903
Source Name
天下一プログラマーコンテスト2012 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
分類たんは、スペースをカンマ区切りにするのが大好き。
でも、スペースが続いたときは、カンマ 1 つで書きたい。
文字列が与えられるので、与えられた文字列のスペースをカンマ区切りにした文字列を出力してください。
入力
c_1c_2…c_N
- 入力として文字列が 1 行で与えられる。
- 入力の文字列長 N は、 1 \leq N \leq 2000 を満たす。
- i 文字目の文字 c_i は大文字のアルファベット (
A
, …,Z
) 、カンマ (,
) 、スペース( - 文字列の最初の文字 c_1 と最後の文字 c_N はスペースではない。
出力
ただし、複数の連続したスペースは 1 つのカンマにする。
なお、行の終端には改行が必要である。
入力例 1
X Y Z
出力例 1
X,Y,Z
入力例 2
A B, C
出力例 2
A,B,,C
入力例 3
QWERTY
出力例 3
QWERTY
Source Name
天下一プログラマーコンテスト2012 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
N 個のグループがあります。
それぞれのグループには、「group1」から「groupN」までの名前がついています。
ある日、あるグループがあるグループを呼び、そして、発言を引用するということが繰り返されました。
groupA が groupB に対して攻撃的であるとします。そのとき
- groupA は groupB を呼ぶとき、グループの名前のうしろに
w
をつけ、「groupBw」 と発言します。 - groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (
"
) で囲んで引用し、うしろにww
をつけて発言します。
また、groupA が groupB に対して攻撃的でないとします。そのとき
- groupA は groupB を呼ぶとき、「groupB」 と発言します。
- groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (
"
) で囲んで引用し、うしろには何もつけずに発言します。
例えば、group2 が group1 に対して攻撃的であるとき、group2 は group1w
と発言します。
さらに、group3 が group2 に対して攻撃的であるとき、group3 は "group1w"ww
と発言します。
また、group2 が group3 に対して攻撃的でないとき、group2 は group3
と発言します。
さらに、group1 が group2 に対して攻撃的でないとき、group1 は "group3"
と発言します。
groupA が groupB に攻撃的だが、groupB がgroupA に攻撃的ではないということもあります。
また、自虐的なグループ、つまり自分自身に対して攻撃的なグループもあります。
ある 1 つの発言が与えられるので、その発言をしそうなグループの総数を答えてください。
入力
N M a_1 b_1 a_2 b_2 : : a_M b_M s
- 1 行目は、グループの数を表す整数 N (1 \leq N \leq 10^5) , 敵対的関係を表す整数 M (1 \leq M \leq 10000) が与えられる。
- 2 行目から M 行は、グループの敵対関係が与えられる。
- a_i, b_i (1 \leq a_i, b_i \leq N) はグループ a_i がグループ b_i に対して攻撃的であることを表す。
- i \neq j ならば、 a_i \neq a_j または b_i \neq b_j である。
- M+2 行目は、あるグループの発言 s が与えられる。
- s の文字列長は 300 以下である。
- 少なくとも 1 グループは発言を行った可能性がある。
部分点
出力
なお、行の終端には改行が必要である。
入力例 1
3 6 1 2 1 3 2 1 2 3 3 1 3 2 "group1w"ww
出力例 1
3
group1w
と発言したのは group2 または group3 である。- group2 が
group1w
と発言した場合、"group1w"ww
と発言したのは group1 または group3 である。 - group3 が
group1w
と発言した場合、"group1w"ww
と発言したのは group1 または group2 である。 - よって、発言
"group1w"ww
を行った可能性のあるグループは、 group1, group2, group3 の 3 グループである。
入力例 2
3 2 1 2 2 3 "group3w"
出力例 2
2
- この発言を行った可能性のあるグループは、 group2, group3 の 2 グループである。
入力例 3
3 1 1 1 ""group1w"ww"ww
出力例 3
1
- 自分自身のグループを呼ぶ場合や、自分自身のグループの発言を引用する場合もある。
Source Name
天下一プログラマーコンテスト2012 予選ATime Limit: 2 sec / Memory Limit: 256 MB
問題文
マス目からなる迷路があります。
迷路の各マスは、巣、角砂糖、壁、空き地のいずれかであり、アリ達は左上にある巣のマスから右下にある角砂糖のあるマスまで行きたいと思っています。
角砂糖のあるマスを含む、壁以外の任意の地点へは到達することができ、またループになっている経路はありません。
加えて、(奇数,奇数) の地点は必ず壁であり、(偶数,偶数) の地点は必ず空き地です。
ここでの座標は、左上の巣のある地点を (0,0) とし、1 つ右の座標は (1,0)、1 つ下の座標は (0,1) になります。
このような迷路の例を図 1 に示します。
黄緑色の部分が (奇数,奇数) の地点、橙色の部分が (偶数,偶数) の地点になります。
ここでのアリは、直進できる場合は直進し、壁にぶつかった場合は 1/2 の確率で左、1/2 の確率で右に曲がる性質を持っています。壁にぶつかっても左右のいずれかに壁がある場合は、その反対方向に必ず曲がります。
どちらにも曲がれないような場合(三方向が壁または迷路外になった場合)は、その場でアリは死亡してしまい壁になります。
なお、巣のマスの下は壁になっているので、最初は右方向にしか進めません。また、角砂糖のあるマスの左は壁になっているので、上方向からしか角砂糖のあるマスに到達できません。
例えば図 1 の場合を図 2 に示すと、1 匹目のアリは直進するので右上の地点 (4,0) で壁と迷路外に囲まれて死亡してしまいます。
2 匹目のアリは (4,0) が 1 匹目のアリにより壁になっているので、その 1 つ手前の (3,0) で死亡し壁になります。
その結果、3 匹目、4 匹目のアリは (2,0) で右に曲がり、(2,4)、(2,3) でそれぞれ死亡します。
5 匹目のアリは (2,2) で直進できないので、(1,2) または (3,2) に進みます。
(1,2) の方向に進んだ場合は (0,4) で死亡しますが、(3,2) の方向に進んだ場合は角砂糖へと到達できます。
アリが角砂糖にに辿り着くまでこのような行動を繰り返したとすると、辿り着くまでに必要なアリの数の期待値を求めなさい。
入力
N c_{(0,0)}c_{(1,0)}‥‥c_{(N-1,0)} c_{(1,1)}c_{(1,1)}‥‥c_{(N-1,1)} : : c_{(0,N-2)}c_{(1,N-2)}‥‥c_{(N-1,N-2)} c_{(0,N-1)}c_{(1,N-1)}‥‥c_{(N-1,N-1)}
- 入力は N+1 行ある。
- 1 行目には、与えられる迷路の縦と横の長さを表す整数 N(5≦N≦49) が与えられる。
- N は奇数である。
- 2 行目からの N 行には、各行に図の形を表す状態 c_{(i,j)}(0≦i,j≦N-1) が N 文字与えられる。
- c_{(i,j)} は下記のいずれかであり、それぞれ地点 (i,j) のマスが下記のような状態であることを表す。
S
: そのマスが巣であることを表す。G
: そのマスに角砂糖があることを表す。#
: そのマスが壁であることを表す。.
: そのマスが空き地であることを表す。
- c_{(0,0)} は必ず
S
であり、c_{(N-1,N-1)} は必ずG
である。また、S
とG
は、それぞれこの場所にしか存在しない。 S
から 1 つ下の地点 c_{(1,0)} とG
から 1 つ左の地点 c_{(N-1,N-2)} は必ず#
である。- i と j が共に奇数の地点は必ず
#
であり、i と j が共に偶数の地点は必ず.
である。
- c_{(i,j)} は下記のいずれかであり、それぞれ地点 (i,j) のマスが下記のような状態であることを表す。
部分点
出力
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 1e−6(10^{-6}) 以下であれば許容する。 なお、行の終端には改行が必要である。
入力例 1
5 S.... ##.## ..... .#.#. .#.#G
出力例 1
5.937500000
- それぞれの匹数で角砂糖まで到達できる確率を求めると、以下のようになる。
- 5 匹で到達できる確率:1/2
- 6 匹で到達できる確率:1/2×1/2
- (2,2) の分岐で 5 匹目は (1,2) の方向へ、6 匹目は (3,2) の方向へ曲がった場合
- 7 匹で到達できる確率:1/2^3
- 8 匹で到達できる確率:1/2^4
- 9 匹で到達できる確率:1/2^4×1
- したがって、5×1/2+6×1/2×1/2+7×1/2^3+8×1/2^4+9×1/2^4×1=5.9375 となる。
入力例 2
9 S........ ####.#### ......... .#####.## ...#.#... .#.#.#### .#...#... .#.#.#.#. .#.#...#G
出力例 2
18.029407501
入力例 3
13 S............ ####.#.#.#### .....#.#...#. .###########. .....#.#..... .#.###.###.## .#...#.#..... ##.#.#.#####. .#.#.....#... .#.###.#.#.## ...#...#..... .#.#.#.#.###. .#.#.#.#...#G
出力例 3
35.000000000