問題文

黒猫のスヌケ君は一人でしりとりをしています。

スヌケ君が使える単語は 26 種類のアルファベットからなる 1 文字以上の文字列全てです。 必ずしも英単語として成立している必要はないことに注意してください。

スヌケ君はしりとりで N 個の単語を使用しました。 これら N 個の単語の長さの合計として考えられる最小値はいくつでしょうか？

制約

• 1≦N≦10^9

入力例 1

4

出力例 1

6

例えば、a → an → n → na というようにしりとりをした場合、単語の長さの合計は 6 となります。

同じ単語を 2 回以上使用してはいけない点に注意してください。

入力例 2

1000

出力例 2

2272

問題文

キリギリスとスローロリスがクリスマスケーキを買うために行列に並びました。

それを見ていたツーリストさんによると以下の情報が分かっています。

• 合計 N 匹の動物が順番に行列に並んだ。
• 行列に並んだ動物は全てキリギリスかスローロリスのどちらかである。
• i 番目に来て行列に並んだ動物はちょうど A_i 匹の動物を順番抜かしした。
• スローロリスがスローロリスを抜かしたことはなかった。

さて、スローロリスは最大で何匹行列に並んでいるでしょうか？

制約

• 1≦N≦300,000
• 0≦A_i≦i-1

入力例 1

3
0 0 1

出力例 1

2

この入力では 3 番目の動物だけが順番抜かしをして、2 番目に来た動物を抜かしました。 そのため、2 番目の動物と 3 番目の動物がスローロリスだということはありえず、スローロリスは 2 匹以下しかいないことが分かります。

また、1 番目の動物と 2 番目の動物がスローロリスだったということはありうるため、答えは 2 匹となります。

入力例 2

4
0 1 2 3

出力例 2

1

この入力では、2 匹以上のスローロリスがいたということはありえません。

入力例 3

7
0 0 1 0 0 2 4

出力例 3

4

問題文

黒猫のスヌケ君はすごろくで遊んでいます。

このすごろくでは変わったサイコロを使っています。 このサイコロには全部で N 個の面があり、それぞれの面が出る確率は全て同じです。 i 番目の面には整数 A_i が書かれていて、この面が出たときは駒をちょうど A_i マス進めます。

一方、このすごろくで使っているマスはそれほど変わったものではありません。 全部で M 個のマスが一列に並んでいて、1 番目のマスがスタート、M 番目のマスがゴールです。 i 番目のマスには整数 B_i が書かれていて、このマスに止まった場合は B_i の値によって以下のような効果を受けます。

• B_i が 0 以上である場合：駒をちょうど B_i マス進める。ただし、進めた先のマスの効果は受けない。
• B_i が 0 未満である場合：-B_i ターン休みとなる。

さて、スヌケ君がこのすごろくでゴールするまでにかかるターン数の期待値はいくらでしょうか？

なお、このすごろくではゴールを越えて進もうとした場合もゴールとみなされます。

制約

• 1≦N≦10^5
• 2≦M≦10^5
• 1≦A_i≦M
• -10≦B_i≦M
• B_1=B_M=0

入力例 1

3 4
1 2 3
0 1 -1 0

出力例 1

2.00000000000000000000

最初のターンで出た目ごとに考えると以下のとおりである。

• 出た目が 1 の場合：1 マス進み、2 番目のマスに止まる。このマスの効果により、3 番目のマスまで進む。次のターンでは何が出てもゴールできるため、ゴールには合計 2 ターンかかる。
• 出た目が 2 の場合：2 マス進み、3 番目のマスに止まる。このマスの効果により、1 ターン休みとなる。次のターンは休みとなり、その次のターンでは何が出てもゴールできるため、ゴールには合計 3 ターンかかる。
• 出た目が 3 の場合：3 マス進み、4 番目のマスに止まる。すなわち、1 ターンでゴールできる。

したがって、期待値は 2/3 + 3/3 + 1/3 = 2 となる。

入力例 2

1 10
1
0 0 0 0 0 0 0 0 0 0

出力例 2

9.00000000000000177636

入力例 3

5 6
1 1 2 3 5
0 0 6 -10 1 0

出力例 3

4.47999999999999953815

問題文

日下部さんは壁に反射するのが大好きで、今日も元気に壁に反射して遊んでいます。

今日の壁は、直角三角形の部屋の壁です。 下図のように三角形の頂点をそれぞれ A,B,C と呼ぶことにします。 日下部さんは頂点 C から点 P に向かってまっすぐ歩き、点 P に着くと、角 BPC = 角 APQ となるような辺 AC 上の点 Q に向かって再びまっすぐ歩きました。

線分 AB の長さは X、線分 BC の長さは Y、線分 AQ の長さは Z でした。 このとき、線分 AP の長さはいくらでしょうか？

制約

• 1≦X,Y≦100
• 1≦Z<\sqrt{X^2+Y^2}
• X,Y,Z は整数である

入力例 1

6 8 5

出力例 1

4

入力例 2

100 100 1

出力例 2

1.40428377656192537870

問題文

以下のようなBNFで表されるベクトル式 S が与えられるので、計算してください。

<expr> ::= <number> | "("<expr>"*"<expr>")" | "("<vector>"*"<vector>")"
<vector> ::= "("<expr>","<expr>")" | "("<expr>"*"<vector>")" | "("<vector>"*"<expr>")"
<number> ::= <digit> | <number><digit>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<expr> の値は整数（スカラー）、<vector> の値は二次元ベクトルとなります。 演算子 * のこの問題での意味は以下の通りです。

• <expr> どうし場合：整数の積を表す。
• <vector> どうしの場合：ベクトルの内積を表す。
• <expr> と <vector> の場合：ベクトルのスカラー倍を表す。

ただし、答えは非常に大きくなることがあるため、998244353 で割った余りで出力してください。

制約

• 1≦|S|≦10^5
• S は問題文中のBNFの <expr> で表される式である。

入力例 1

((1,2)*(3,4))

出力例 1

11

ベクトル (1,2) とベクトル (3,4) の内積を計算すると 1*3 + 2*4 = 11 となります。

入力例 2

((((1*2),3)*4)*(((5,6)*(7,8))*(9,10)))

出力例 2

15936

入力例 3

0000000000099824435399824435399824435399824435399824435398

出力例 3

98

問題文

文字列 S と Q 個のクエリが与えらます。

i 番目のクエリでは文字列 T_i が与えられるので、T_i を部分列として含むような S の極小な部分文字列のうち最も左にあるものを求めてください。

ただし文字列 s が極小であるとは、s の部分文字列であって T_i を部分列として含むような s より短いものが存在しないことを指すものとします。

制約

• 1≦|S|≦10^5
• 1≦Q≦10^5
• 1≦|T_i|
• |T_i| の和は 10^5 を越えない
• S, T_i は小文字アルファベットのみからなる

入力例 1

aaxbab
12
ab
da
subsequence
aaxbab
a
aa
aaa
aaaa
ba
x
xb
xb

出力例 1

2 4
-1
-1
1 6
1 1
1 2
1 5
-1
4 5
3 3
3 4
3 4

1 番目のクエリについて説明します。

答えは 2 文字目から 4 文字目までの部分文字列 axb となります。

他にも　5 文字目から 6 文字目までの部分文字列 ab も T_1 を部分列として含む極小な部分文字列ですが、axb の方が左にあるためこちらは答えとはなりません。

また、aaxb は極小ではありません。 なぜなら axb という T_i を部分列として含むような部分文字列を含むためです。

問題文

ツーリストさんは 2 つのリストを持っています。

2 つのリストの長さはいずれも N で、i 個目のリストの j 番目は A_{i,j} です。 A_{i,j} は正または負の整数で、0 ではありません。

ツーリストさんはこれらのリストに対して以下のような操作を行おうとしています。

• まず、2 つのリストに含まれる負の整数を全て正の整数に書き換える。このとき、元々同じだった数は同じ数に、異なっていた数は異なった数に書き換えなければならない。
• 次に、縦 2 マス横 N マスのマス目が書かれた紙を用意し、i 行目 j 列目のマスに i 個目のリストの j 番目の数を書き込む。
• 最後に、隣接したマスに異なる数が書き込まれているような辺と外枠をはさみで切る。すると紙はいくつかのピースに分かれるので、その個数を数える。

ツーリストさんは、うまく負の整数を書き換えることで、分かれるピースの個数をできるだけ少なくしようとしています。 紙はいくつのピースに分かれるでしょうか？

制約

• 1≦N≦10^5
• 1≦|A_{i,j}|≦300

入力例 1

5
1 2 1 2 1
-1 -2 -3 -3 -3

出力例 1

5

例えば -1 を 999 に、-2 を 2 に、-3 を 1 に書き換えると下図のようになり、ピース数は最小の 5 個となります。

入力例 2

15
1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1
2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3

出力例 2

9

問題文

イベルタルは Y 字型のポケモンです。

イベルタルは二次元グリッドの座標 (0,0) にいて、座標 (X,Y) にある巣へ帰ろうとしています。

イベルタルは上・右・左下の三方向に 1 秒で移動することができます。 つまり、座標 (x,y) からは、座標 (x,y+1) または座標 (x+1,y) または座標 (x-1,y-1) に 1 秒で移動することができます。 また、イベルタルは同じ方向に連続で 2 回以上移動することはできません。

このとき、イベルタルが巣に帰るためにかかる秒数の最小値はいくらでしょうか？

制約

• -10^9≦X,Y≦10^9

入力例 1

2 0

出力例 1

5

図のように移動するのが最短で、5 秒かかります。 同じ方向に 2 回以上連続で移動できない点に注意してください。

入力例 2

-2 -3

出力例 2

7

入力例 3

-1000000000 1000000000

出力例 3

5999999997

入力例 4

0 0

出力例 4

0

問題文

1 辺が 4000 マスのチェス盤があり、その上にルークが N 置かれています。 i 番目のルークは R_i 行目 C_i 列目のマスに置かれています。

それを見た黒猫のスヌケ君は出来るだけ少ない個数のルークを取り除くことによって、どの行や列にもルークが高々 1 個しかないようにしたいと考えました。 スヌケ君はいくつのルークを取り除けばいいでしょうか？ また、その個数を達成するために必ず取り除かなければいけないルーク、絶対に取り除いてはいけないルークがどれなのかも求めてください。

制約

• 1≦N≦40000
• 1≦R_i,C_i≦4000
• 同じマスに複数のルークが置かれていることはない

入力例 1

6
1 1
1 3
2 1
2 2
2 3
3 2

出力例 1

3
0
0
0
1
0
-1

取り除く個数が最小になるようなルークの取り除き方は下図のような 2 通りが考えられますが、 4 番目のルークはいずれにおいても取り除かれており、6 番目のルークはいずれにおいても取り除かれていません。

入力例 2

9
1 2
2 2
2 1
3 3
4 6
4 5
4 4
5 4
6 4

出力例 2

4
-1
1
-1
-1
0
0
1
0
0

問題文

約数の和が 98 になるような整数を全て求めてください。

問題文

黒猫のスヌケ君は「パンプキン２」というカードゲームで遊んでいます。

そこでスヌケ君は以下のような問題を考えることにしました。

今、スヌケ君の手元に N 枚のカードがあります。 i 番目のカードのコストは C_i、ゲインは G_i です。

スヌケ君は各カードについて以下のどちらかの操作を 1 度だけ行うことができます。

• 抽出：カードのゲインの値だけマナが増える。ただし、スヌケ君が最初に持っているマナは 0 である。
• 召喚：カードのコストの値だけマナを消費することによって、そのカードを召喚することができる。ただし、マナが足りない場合は召喚を行うことはできない。

操作を行うカードは好きな順番で選ぶことができます。

このとき、スヌケ君が召喚できるカードは最大で何枚でしょうか？

制約

• 1≦N≦10^5
• 0≦C_i≦10^9
• 0≦G_i≦10^9

入力例 1

5
3 0
0 4
2 1
2 0
1 3

出力例 1

3

例えば以下のように操作を行えば、3 枚のカードを召喚することができます。

• 5 番目のカードを抽出する。マナは 3 に増える。
• 3 番目のカードを召喚する。マナは 1 に減る。
• 2 番目のカードを抽出する。マナは 5 に増える。
• 1 番目のカードを召喚する。マナは 2 に減る。
• 4 番目のカードを召喚する。マナは 0 に減る。

入力例 2

7
1 0
2 1
3 1
3 2
3 2
4 0
5 5

出力例 2

3

入力例 3

1
1 0

出力例 3

0

この入力では 1 枚も召喚できません。