A - 数え上げ

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

問題文

シカのAtCoDeerくんは数え上げ問題が大好きです。数え上げ問題のmodの値としてよく出てくるものに10^N +7 の形のものがあります。Nが与えられるので、整数10^N +7を計算してください。

制約

  • Nは整数
  • 1≦N≦100

入力

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

N

出力

10^N +7を出力せよ。

入力例1

9

出力例1

1000000007

見慣れたmodです。

入力例2

3

出力例2

1007

1007は素数ではありませんが、1007を出力してください。

入力例3

50

出力例3

100000000000000000000000000000000000000000000000007

答えは64bit整数に収まらない場合があります。

B - せんべい

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

問題文

シカのAtCoDeerくんはせんべいが好きです。今、AtCoDeerくんは1～Nの番号のついたN枚のせんべいをくれると噂の高橋くんに目をつけました。番号が大きい方が大きくて価値があるので、AtCoDeer君は番号Nのせんべいは絶対に食べたいと考えました。しかし、AtCoDeerくんはお腹がいっぱいになるためK枚までしかせんべいを食べることが出来ません。

高橋くんは事前にN枚のせんべいを並び替え、一枚ずつ順にせんべいをAtCoDeerくんにあげようとします。AtCoDeerくんはi(1≦i≦N)枚目をもらうとき、そのせんべいを食べるかどうかをその時点で選択します。しかし、既にK枚食べている場合は、これ以上食べることは出来ません。食べない場合は高橋くんがそのせんべいを食べるので、後になってAtCoDeerくんがそのせんべいを食べることは出来ません。AtCoDeerくんはせんべいを見てもその番号はわかりませんが、既に見た(食べたものも含む)全てのせんべいの大小を比べることは出来ます。

高橋くんがせんべいをあげる順番はランダム(N!個の順列のうちから等確率で選ばれる)で、AtCoDeerくんには事前にはわかりません。 AtCoDeerくんが最適な戦略をとった時、最終的に番号NのせんべいをAtCoDeerくんが食べられる確率を求めてください。

制約

  • 1≦K≦N≦1000

入力

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

N K

出力

AtCoDeerくんが最適な戦略をとった時に最終的にせんべいNを食べられる確率を出力せよ。出力は絶対誤差または相対誤差が10^{-6}以下であれば許容される。

入力例1

3 1

出力例1

0.500000000000

次のような戦略が最適です。

  • 1枚目は食べない。
  • 2枚目は、1枚目より大きければ食べる。
  • 3枚目は、まだ食べられるなら(2枚目を食べていないなら)食べる。
この時、せんべいを見る順番が1,3,2 と 2,1,3 と 2,3,1 の時はせんべい3を食べることが出来るので、確率は3/3! = 1/2 です。

入力例2

17 17

出力例2

1.000000000000

全てのせんべいを食べることが出来るので、求める確率は1です。

入力例3

1000 10

出力例3

0.984898795563
C - ABCAC

実行時間制限: 5 sec / メモリ制限: 256 MB

問題文

シカのAtCoDeerくんは、たかいたい(高い鯛)が大好きです。ところでこの文字列は空でない文字列A,B,Cを使ってABCAC(文字列を連結したもの)と書けます(A="た",B="か",C="い")。そこで、AtCoDeerくんは文字列Sに対して、このような分割が何通りあるか求めることにしました。

制約

  • 5≦|S|≦200000
  • S は英小文字のみからなる。

入力

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

S

部分点

この問題には部分点が設定されている。

  • |S|≦2000を満たすデータセットに正解した場合、部分点として20点が与えられる。

出力

S=ABCACと書けるような非空文字列の組{A,B,C}が何通りあるか出力せよ。

入力例1

takaitai

出力例1

2

A="ta",B="ka",C="i" と,A="t",B="ak",C="ai" の2通りがある。

入力例2

aaaaaaaaaa

出力例2

6

以下の6通りである。

  • A="aaa",B="aa",C="a"
  • A="aa",B="aa",C="aa"
  • A="aa",B="aaaa",C="a"
  • A="a",B="aa",C="aaa"
  • A="a",B="aaaa",C="aa"
  • A="a",B="aaaaaa",C="a"

入力例3

abcabc

出力例3

0

A,B,Cとして空文字列はとれないことに注意せよ。

D - 隠された等差数列

実行時間制限: 5 sec / メモリ制限: 256 MB

問題文

シカのAtCoDeerくんはある日N項からなる数字列{d_i} (0≦i≦N-1)を見つけました。AtCoDeerくんの勘によると、この裏には非負整数からなる等差数列が隠れています。具体的には、

  • 非負整数A,B,正整数Xをとる。
  • a_0 = A , a_i = a_{i-1} + B (1≦i≦N-1) とa_iを定める。
  • すると、i (0≦i≦N-1) に対し、a_iの(十進表記で)下からX桁目がd_iに等しい。
ここで、非負整数nの下からx桁目とは、 (n/10^{x-1})%10 のことを指す(ただし, /は除算(切り捨て), %はあまりを取る操作)。 例えば、102の下から一桁目は2,二桁目は0,三桁目は1,四桁目は0,百桁目は0である。

AtCoDeerくんは、このような条件を満たす等差数列の内、初項(すなわちA)が最小のものを求めることにした。

制約

  • 1≦N≦10^4
  • 各0≦i≦N-1に対し,d_iは0以上9以下の整数
  • d_0≠0

入力

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

d_0d_1....d_{N-1}
空白文字で区切られずに与えられることに注意せよ。

出力

条件を満たす等差数列の内の初項の最小値を出力せよ。そのような等差数列が存在しない場合は-1を出力せよ。

入力例1

6925814703

出力例1

6

A=6,B=3,X=1は条件を満たし、これがAの最小です。

入力例2

6925814704

出力例2

61

A=61,B=31,X=2が条件を満たします。

入力例3

6925814705

出力例3

-1

条件を満たす等差数列はありません。

入力例4

9

出力例4

9