問題文

二つの自然数 a, b に対して、うく数列を以下のように定義する。

u_1 = a, u_2 = b, u_{k+2} = u_k + u_{k+1} (1 \leq k)

2 以上の自然数 X_i がT 個与えられるので、各 X_i に対し、X_i を含むようなうく数列の中で辞書順最小のものを求めるプログラムを作成せよ。

制約

• 1 \leq T \leq 100
• 2 \leq X_i \leq 10^{18}
• 入力は全て整数

入力例 1

3
14
233
100

出力例 1

1 4
1 1
1 99

a = 1, b = 4 のとき、うく数列は以下のようになる

{1, 4, 5, 9, 14, ..}

問題文

1, 2, ..., N の N 個の甜菜が順番に植えられている。 甜菜 i には水を最大で A_i 与えることができる。A_i より多くの水を与えると、その甜菜はふやけて枯れてしまう。

これから最大 M 回のスプリンクラーの操作によって、甜菜に水を与えることができる。スプリンクラーでは 1 回の操作で、連続する範囲を選んで範囲内にある甜菜に一様に水を 1 与えることができる。

スプリンクラーの操作によってなるべく多くの水を甜菜たちに与えたい。すべての甜菜を枯らさないという条件のもとで、甜菜たちに与えることのできる水の量の合計の最大値を求めよ。

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^{14}
• 1 \leq A_i \leq 10^9
• i \neq j ならば A_i \neq A_j
• 入力は全て整数

入力例 1

4 4
1 4 2 5

出力例 1

9

例えば、 次のようにスプリンクラーの操作を行う。

• 区間 [1, 4] に水を与える(合計 4)。
• 区間 [2, 4] に水を与える(合計 7)。
• 区間 [2, 2] に水を与える(合計 8)。
• 区間 [4, 4] に水を与える(合計 9)。

入力例 2

4 6
10 9 4 11

出力例 2

20

入力例 3

1 100000000000000
1

出力例 3

1

問題文

うしくんとうくくんが H \times W マスの迷路の中に閉じ込められてしまった。
とりあえず、いつのまにかポケットに入っていた地図を元に合流したい。

地図によると迷路は以下の6種類のマスからできているようだ。

# 壁       通ることはできない
. 床       隣接する上下左右方向に移動できる(必ずしも移動する必要はない)
> 動く床(右)   右方向のみに移動できる(必ず移動を試みる)
< 動く床(左)   左方向のみに移動できる(必ず移動を試みる)
^ 動く床(上)   上方向のみに移動できる(必ず移動を試みる)
v 動く床(下)   下方向のみに移動できる(必ず移動を試みる)

壁の存在する方向に移動しようとした場合、移動できず移動元のマスに留まる。

うしくんとうくくんの初期位置の候補が Q 個与えられるので、各初期位置について、二人が合流するまでにかかる最短の移動回数を求めよ。

一回の移動の際にはうしくんとうくくんは独立に行動できる。また、うしくんとうくくんは心が通じ合っているので、お互いに最適な行動を取ることが可能である。

制約

• 3 \leq H, W \leq 30
• 1 \leq Q \leq 10^5
• S_i (1 \leq i \leq H) は上記の 6 種類の文字のみからなる長さ W の文字列である。
• 2 \leq SX_i, GX_i \leq W - 1 (1 \leq i \leq Q)
• 2 \leq SY_i, GY_i \leq H - 1 (1 \leq i \leq Q)
• 与えられる入力において、迷路の外側 1 マスは壁で囲われていることが保証されている。
• 与えられる入力において、うしくんとうくくんの初期位置に壁があることはない。

入力例 1

5 4 3
####
#..#
#.##
##.#
####
2 2 2 2
2 3 3 2
2 2 3 4

出力例 1

0
1
-1

最初から同じマスにいることもあります。 動く床が一つもないこともあります。

入力例 2

5 5 2
#####
#<..#
###^#
#...#
#####
4 2 2 4
2 2 2 4

出力例 2

3
6

入力例 3

10 13 10
#############
#vvv>vvv#v<.#
#.^.^<#>.v<.#
#.#>v<<<>>v.#
#^v<.v^v>#<<#
#^.>vv^.^.^^#
#<><vv>^vv^>#
##<.>^>v.^<<#
#.v.^v.>><v^#
#############
10 4 8 6
11 7 11 5
8 9 7 8
12 4 5 6
5 6 8 6
12 3 11 7
2 5 8 9
10 4 6 8
4 3 4 3
7 7 3 6

出力例 3

-1
2
3
-1
10
3
-1
-1
0
9

問題文

ある日ukuさんは自分の名前が奇数長の回文になっていることに気がついた。

うくさんは長さ N の文字列 S を持っている。

うくさんは Q 個の連続な部分文字列 S[L_i:R_i] について、最長の奇数長回文の長さを求めたくなった。

めんどくさがりやなうくさんに代わって、それを求めるプログラムを作成せよ。

(15:24追記) 求める奇数長回文も連続である必要があります。

制約

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• S は小文字アルファベットのみからなる長さ N の文字列である
• 1 \leq L_i \leq R_i \leq N

入力例 1

10 3
ukunichiaa
1 10
1 3
9 10

出力例 1

3
3
1

求めるのは奇数長の回文の長さなので、”aa”は条件を満たさないことに注意してください。

入力例 2

9 3
ababcbaba
1 5
1 7
1 9

出力例 2

3
5
9

問題文

1 から N まで番号づけされた N 人のうくさんと、N+1 から 2N まで番号づけされた N 人のひふみさんがいる。

すべての i(1 \leq i \leq N) に対して、i 番目のうくさん と i+N 番目のひふみさん同士はカップルであることが分かっている。

今、2N 個の椅子が横 1 列に並んでいて、既に N 人のうくさんは座っている。j 番目のうくさんは左から P_j 番目の椅子に座っている。

これから、N 人のひふみさんが空いている椅子に座る。ただし、カップルが隣接した椅子に座るとその人同士でいちゃつくので、それが存在するような配置は避けたい。

条件を満たす座り方の数を 924844033 で割った余りで求めよ。

制約

• 1 \leq N \leq 10^5
• 1 \leq P_j \leq 2N
• j \neq k ならば P_j \neq P_k
• 入力は全て整数

入力例 1

2
1
2

出力例 1

1

条件を満たす座り方は 1234 の 1 通りである。 例えば 1243 は 2 番目のうくさんと 4 番目のひふみさんが隣接しているため条件を満たさない。

入力例 2

3
1
2
6

出力例 2

3

124653、126453、126543 の 3 通りである。

入力例 3

10
2
3
5
6
8
9
11
12
13
14

出力例 3

1561440