問題文

座標平面上の点 P(X, Y) を、次の操作を繰り返して原点に動かしたいです。

• ある実数 a を選び、 P の現在の座標を (x, y) として、 P を (x, a) または (a, y) に動かす。

必要な最小の操作回数を求めてください。

制約

• 0 \leq X, Y \leq 100
• 入力は全て整数

入力例 1

6 4

出力例 1

2

次のように操作を行うことで、 2 回の移動によって P を原点まで動かせます。
　　1 回目 … a = 0 として、P を (6, 4) から (0, 4) に移動させる。
　　2 回目 … a = 0 として、P を (0, 4) から (0, 0) に移動させる。
2 回未満の移動で P を原点まで動かすことはできないので、これが最適です。

入力例 2

0 1

出力例 2

1

問題文

XXXX 年のパ研合宿には N 人の参加者がいました。

パソコンを充電するために 1 人 1 つのコンセントが必要です。しかし、会場には使用可能なコンセントが 1 つしかありませんでした。そのため、運営は M 個口の電源タップをいくつか用意することにしました。

M 個口の電源タップ 1 つを未使用の使用可能なコンセント 1 つに挿すことで、新たに使用可能なコンセントが M 個できます。

参加者 1 人につき最低でも 1 つ使用可能なコンセントがあるようにするには最低で何個の電源タップを用意する必要がありますか？　ただし、1 人 1 つのコンセントを用意することが不可能である場合はそのことを報告してください。

制約

• 1 \leq N,M \leq 10^9
• 入力は全て整数

入力例 1

5 5

出力例 1

1

元のコンセントに 1 個電源タップを指すと 5 個コンセント口ができるので人数分用意できます。

入力例 2

30 1

出力例 2

-1

1 個口の電源タップだけでは人数分用意することができません。

入力例 3

998244353 3

出力例 3

499122176

問題文

英小文字と ? のみからなる文字列 S が与えられます。

文字列 S に含まれる ? をそれぞれ好きな英小文字に置き換えることで作れる回文は何通りあるか求めてください。

ただし、答えは非常に大きくなる可能性があるので、 998244353 で割ったあまりを出力してください。

制約

• 1 \leq | S | \leq 200000
• S は英小文字と ? のみからなる

入力例 1

a??

出力例 1

26

aaa、aba、aca など、全部で 26 通りの回文を作ることができます。

入力例 2

atcoder

出力例 2

0

回文を作ることはできません。

入力例 3

?????????????

出力例 3

45855352

答えを 998244353 で割ったあまりを出力することに注意してください。

問題文

N 個の椅子が横一列に並んでいます。これらの椅子に K 人の人を座らせます。1 つの椅子に座る人は高々 1 人である必要があります。このとき次の条件を満たす i \,(2 \leq i \leq N-1) の個数を最小化したいです。

• 左から i-1 , i , i+1 番目の椅子全てに人が座っている

このような座り方を一つ見つけてください。

制約

• 3 \leq N \leq 2 \times {10^5}
• 1 \leq K \leq N
• 入力は全て整数

入力例 1

6 4

出力例 1

1 2 4 6 

A = (1, 2, 4, 6) とすれば、これは題意を満たします。ほかにも、 A = (2, 3, 5, 6) , (1, 2, 5, 6) なども正解となります。

入力例 2

6 5

出力例 2

1 2 4 5 6 

問題文

縦の長さが H 、横の長さが W の長方形の中に半径の長さが等しい 2 つの円板を入れることを考えます。このとき、円板が長方形からはみ出したり、2 つの円板の共通部分の面積が 0 より大きくなったりしてはいけません。このとき、円板の半径の最大値を解答してください。

制約

• 1 \leq H,W \leq {10^9}
• 入力は全て整数

入力例 1

6 4

出力例 1

1.535898384862246

下図のようにして円板を置くことで、円板の半径の長さを 5-2\sqrt{3} (\approx {1.5358983}) とすることができます。円板の半径の長さをさらに長くすることはできないため、この値を出力します。

入力例 2

4 1

出力例 2

0.500000000000000

問題文

パ研合宿の K 運営長はある一日に開催するイベントを何にするか決めたいです。

現在 N 個のイベントの候補があり、パ研合宿の参加者は M 人です。 i 個目のイベントの時間の長さは L_i です。また、i 個目のイベントに対する j 人目の参加者の満足度は A_{i,j} です。

1 個以上の行うイベントを定めたとき、そのイベントの集合に対する良さは全ての人に対してのイベントの満足度の最大値の総和と定義されます。

一日の時間は限られているため、イベントの時間の長さの合計は D 以下である必要があります。このとき、行うイベントの集合の良さは最大でいくつになりますか？

ただし、イベントを一個も行うことができない場合はそのことを報告してください。

制約

• 1 \leq N,M \leq 18
• 1 \leq D \leq 10^9
• 1 \leq L_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq A_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
• 入力は全て整数

入力例 1

2 4 10
5 6
1 2 3 4
5 6 7 8

出力例 1

26

二つ目のイベントのみを行うのが最適です。

入力例 2

1 4 10
11
3 6 1 8

出力例 2

-1

イベントを行うことができません。

入力例 3

4 8 100
30 40 50 110
3 1 4 1 5 9 2 6
5 3 5 8 9 7 9 3
2 3 8 4 6 2 6 4
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

54

問題文

N 頂点の根付き木が与えられます。頂点には 1 から N までの番号が振られており、根は頂点 1 で、頂点 i\,(2\leq i\leq N) の親は頂点 P_i です。

Q 個の質問が与えられるので答えてください。

i 番目の質問では整数 X_i, Y_i が与えられます。頂点 X_i は頂点 Y_i の祖先であり、二頂点間の距離を d とすると d\geq2 です。頂点 X_i と Y_i を結ぶパス上の頂点の番号を順に v_0,v_1,\ldots,v_d （ただし、v_0=X_i, v_d=Y_i）とするとき、v_1 を出力してください。

制約

• 3\leq N\leq 2\cdot 10^5
• 1\leq P_i\leq i-1\, (2\leq i\leq N)
• 1\leq Q\leq 2\cdot 10^5
• 1\leq X_i,Y_i\leq N\, (1\leq i\leq Q)
• 頂点 X_i は頂点 Y_i の祖先 (1\leq i\leq Q)
• 頂点 X_i と頂点 Y_i の距離は 2 以上

入力例 1

7
1 1 3 3 5 5
3
1 7
3 6
3 7

出力例 1

3
5
5

1 番目のクエリにおいて、(v_0,v_1,v_2,v_3)=(1,3,5,7) であり、v_1=3 です。

2 番目のクエリにおいて、(v_0,v_1,v_2)=(3,5,6) であり、v_1=5 です。

3 番目のクエリにおいて、(v_0,v_1,v_2)=(3,5,7) であり、v_1=5 です。

入力例 2

7
1 2 3 4 5 6
5
1 6
2 5
3 7
3 7
1 4

出力例 2

2
3
4
4
2

入力例 3

7
1 1 1 4 3 2
3
1 6
1 7
1 5

出力例 3

3
2
4

問題文

hiikunZ 君はクイズ大会の主催者ですが、得点の管理が苦手です。そこで、あなたが「アタックサバイバル」というルールにおいて得点の管理を行うプログラムを書いてあげることにしました。以下の問題を解くプログラムを書いてください。

クイズ大会に N 人の参加者が参加していて、 1 から N までの番号がつけられています。各参加者は「体力」というパラメータを持っています。はじめ、参加者 i の体力は A_i です。そして Q 回、以下の 2 種類のイベントが発生します。

• 1 x y : 参加者 x が配点 y の問題に正解する。すると、参加者 x 以外の体力が 0 より大きいすべての参加者の体力が y 減る。
• 2 x y : 参加者 x が配点 y の問題に誤答する。すると、参加者 x の体力が y 減る。

各イベントごとに、イベントの前には体力が 0 より大きかったが、イベントの後には体力が 0 以下になった参加者の番号を昇順に列挙してください。

制約

• 1 \leq N,Q \leq 200000
• 1 \leq A_i \leq 10^9
• 1 \leq x \leq N
• 1 \leq y \leq 10^9
• 各イベントの発生前、参加者 x は体力が 0 より大きい
• 入力はすべて整数

入力例 1

4 2
5 5 5 10
1 2 5
2 4 5

出力例 1

2 1 3
1 4

最初、各参加者の体力は (5,5,5,10) です。

1 回目のイベントのあと、各参加者の体力は (0,5,0,5) になります。

1 回目のイベントの前には体力が 0 より大きかったが、その後に体力が 0 以下になった参加者は 参加者 1 と 参加者 3 の 2 人です。

2 回目のイベントのあと、各参加者の体力は (0,5,0,0) になります。

2 回目のイベントの前には体力が 0 より大きかったが、その後に体力が 0 以下になった参加者は 参加者 4 の 1 人です。

入力例 2

4 3
20 10 5 5
1 2 1
1 2 500
2 2 500

出力例 2

0
3 1 3 4
1 2

問題文

あなたは長さ N の数列 X=(X_1,X_2,\ldots,X_N) を持っていましたが、X の各要素の具体的な値は忘れてしまいました。あなたは次のことを覚えています。

• (15:18 修正) X のすべての要素は正整数である。
• i=1,2,\ldots,P について、X_{A_i}=X_{B_i}
• i=1,2,\ldots,Q について、X_{C_i}\neq X_{D_i}

X として考えられるもののうち、辞書順で最小のものを求めてください。ただし、X として考えられるものが存在しない場合はそのことを報告してください。

制約

• 2\leq N\leq 2\times 10^5
• 1\leq P,Q\leq 10^5
• 1\leq A_i<B_i\leq N\,(1\leq i\leq P)
• 1\leq C_i<D_i\leq N\,(1\leq i\leq Q)
• 入力はすべて整数

入力例 1

5 2 3
1 2
2 4
1 3
4 5
3 5

出力例 1

1 1 2 1 3

X として考えられるものに (2,2,1,2,4) や (100,100,10,100,1) などもありますが、(1,1,2,1,3) が辞書順で最小です。

入力例 2

5 1 1
1 2
1 2

出力例 2

-1

X_1=X_2 と X_1\neq X_2 を同時に満たすことはできません。

問題文

パ研王国には N 個の街があり、 1,2,3,\ldots,N と番号がついています。

王国には N-1 本の道路があり、 i 本目の道路は街 A_i と街 B_i を結んでいて、C_i という重みが定まっています。パ研王国のすべての街は道路を使って行き来することができます。

パ研王国の K 国王は変わっているので、 Q 個の街の組をあなたに言い渡し、各組 (S_i,T_i)(1 \leq i \leq Q) について街 S_i から街 T_i へのパス上の道路の重みの中央値を求めたいと言いました。召使のあなたは K 国王の代わりに王が求めたい値を求めてあげてください。

(2023/03/27 15:36追記:) 数列 X に対する中央値は、要素数が偶数の場合は要素を昇順に並べた列を X_1,X_2,...,X_n とするとき、(X_{n/2} + X_{n/2+1}) / 2 で定義されます。 奇数の場合は、要素を昇順に並べた列を X_1,X_2,...,X_n とするとき、X_{(n+1)/2} で定義されます。

制約

• 2 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq N (1 \leq i \leq N-1)
• 2 \leq C_i \leq 2 \times 10^5 (1 \leq i \leq N-1)
• C_i はすべて偶数(1 \leq i \leq N-1)
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq S_i,T_i \leq N (1 \leq i \leq Q)
• S_i \neq T_i (1 \leq i \leq Q)

入力例 1

5
1 2 50
2 3 100
1 4 20
4 5 30
1
3 5

出力例 1

40

入力例 2

3
1 2 100
2 3 50
1
1 3

出力例 2

75

問題文

数列 X=(X_1,X_2,\ldots,X_M) の美しさを以下のように定めます。

• Y_i\coloneqq \max(X_1,X_2,\ldots,X_i) としたときの、Y_1,Y_2,\ldots,Y_M に含まれる数の種類数

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。Q 個のクエリを処理してください。

i 番目のクエリでは整数 L_i,R_i が与えられるので、数列 (A_{L_i},A_{L_i+1},\ldots,A_{R_i}) の美しさを出力してください。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq A_i\leq N\,(1\leq i\leq N)
• 1\leq Q\leq 2\times 10^5
• 1\leq L_i\leq R_i\leq N\,(1\leq i\leq Q)
• 入力はすべて整数 (17:15 追記)

入力例 1

5
1 5 2 4 3
4
1 5
2 5
3 3
3 5

出力例 1

2
1
1
2

(1,5,2,4,3) の美しさは 2 であるため、1 番目のクエリに対しては 2 を出力します。

(5,2,4,3) の美しさは 1 であるため、2 番目のクエリに対しては 1 を出力します。

入力例 2

5
3 2 2 4 5
4
1 5
1 5
4 5
4 5

出力例 2

3
3
2
2

(L_i,R_i)=(L_j,R_j) となる i,j\,(i\neq j) が存在する場合もあります。

入力例 3

5
4 4 1 3 5
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

出力例 3

1
1
1
1
2
1
1
1
2
1
2
3
1
2
1

問題文

有限個の非負整数からなる多重集合 S に対して、\operatorname{mex}(S) を S に含まれない最小の非負整数と定義します。例えば、\operatorname{mex}(\lbrace 0,0,1,3 \rbrace)=2,\operatorname{mex}(\lbrace 1 \rbrace)=0,\operatorname{mex}(\lbrace\rbrace)=0 です。

黒板に長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が書かれています。

あなたは、以下の操作をちょうど K 回行います。

• A の中から非負整数を 0 個以上選ぶ。選んだ非負整数からなる多重集合を S として、\operatorname{mex}(S) を A の後ろに追加する。

最終的に黒板に書かれている非負整数列 A としてありうるものの個数を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq N, K \leq 2000
• 0 \leq A_i \leq 2000
• 入力される数値は全て整数

入力例 1

3 1
0 1 3

出力例 1

3

操作後に得られる数列は、以下の 3 通りです。

• (0,1,3,0)
• (0,1,3,1)
• (0,1,3,2)

入力例 2

5 10
3 1 4 1 5

出力例 2

14476910

問題文

頂点 1 を根とする N 頂点の根付き木があります。頂点 i の親は頂点 P_i です。これから各頂点に 0 または 1 を書き込みたいです。

以下の与えられた条件を満たすような頂点に対する 0 と 1 の割り当て方を一つ求めてください。また、そのような割り当て方が存在しない場合はそのことを報告してください。

• K 個の頂点 M_1 ,M_2, \cdots M_K にはそれぞれ S_1 ,S_2, \cdots S_K が書き込まれている。
• 頂点 i に 1 が書き込まれているならば、頂点 A_i とその子孫の頂点には 1 が書き込まれている。
• 頂点 i に 0 が書き込まれているならば、頂点 A_i とその子孫の頂点には 0 が書き込まれている。

制約

• 2 \leq N \leq 10^5
• 1 \leq P_i < i (2 \leq i \leq N)
• 0 \leq K \leq N-1
• 1 \leq M_i \leq N (1 \leq i \leq K)
• M_i \neq M_j (1 \leq i < j \leq K)
• S_i \in \lbrace 0,1 \rbrace (1 \leq i \leq K)
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 入力は全て整数

入力例 1

4
1 1 2
1
2 1
3 4 3 2

出力例 1

1111

入力例 2

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

出力例 2

IMPOSSIBLE

問題文

はじめに整数 T が与えられます。T 個のテストケースについて次の問題を解いてください。

hiikunZ 君は、誕生日プレゼントとしてパ研マシンをもらいました。

パ研マシンには、ディスプレイ、ライト、ボタンが 1 つずつついています。

はじめ、ディスプレイには整数 s が表示されていて、ライトは赤に点灯しています。

hiikunZ 君がボタンを押すたびに、ディスプレイに表示される整数 x とライトの色は、次の通りに変化します。

• ボタンを押す前に、ライトが赤に点灯していた場合、x は A_r \times x + B_r を素数 P で割ったあまりに変化し、ライトは青に点灯する。
• ボタンを押す前に、ライトが青に点灯していた場合、x は A_b \times x + B_b を素数 P で割ったあまりに変化し、ライトは黄に点灯する。
• ボタンを押す前に、ライトが黄に点灯していた場合、x は A_y \times x + B_y を素数 P で割ったあまりに変化し、ライトは赤に点灯する。

hiikunZ 君はボタンを何回か ( 0 回でもよい ) 押すことでディスプレイに表示されている整数を t に変化させたいです。

これが可能かどうか判定し、可能な場合はこれを達成するために必要なボタンを押す回数の最小値を求めてください。

制約

• 1 \leq T \leq 10
• 2 \leq P \leq 10^9
• P は素数
• 0 \leq A_r,A_b,A_y < P
• 0 \leq B_r,B_b,B_y < P
• 0 \leq s,t < P
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。ここで test_i は i 番目のテストケースを意味します。

T
test_1
test_2
\vdots
test_T

各テストケースは以下の形式で与えられます。

s t P
A_r B_r A_b B_b A_y B_y

出力

答えを T 行にわたって出力してください。

i (1 \leq i \leq T) 行目には、 i 番目のテストケースにおいて、ディスプレイに表示されている整数を t に変化させるのに必要なボタンを押す回数の最小値を出力してください。ただし、これが不可能な場合は代わりに -1 と出力してください。

入力例 1

3
1 8 13
1 2 3 4 5 6
0 1 3
1 0 1 0 1 0
123456789 634 998244353
1 23 456 7890 123456789 987654321

出力例 1

4
-1
164941630

1 番目のテストケースにおいて考えます。

ライトの色と、ディスプレイに表示されている整数はボタンを押すたびに次のように変化します。

• 最初、ライトは赤に点灯していて、ディスプレイには整数 1 が表示されています。
• 1 回目にボタンを押したとき、ディスプレイに表示されている整数は 1 \times 1 + 2 = 3 を 13 で割ったあまりである 3 に変化し、ライトは青に点灯します。
• 2 回目にボタンを押したとき、ディスプレイに表示されている整数は 3 \times 3 + 4 = 13 を 13 で割ったあまりである 0 に変化し、ライトは黄に点灯します。
• 3 回目にボタンを押したとき、ディスプレイに表示されている整数は 5 \times 0 + 6 = 6 を 13 で割ったあまりである 6 に変化し、ライトは赤に点灯します。
• 4 回目にボタンを押したとき、ディスプレイに表示されている整数は 1 \times 6 + 2 = 8 を 13 で割ったあまりである 8 に変化し、ライトは青に点灯します。

つまり、4 回ボタンを押すことでディスプレイに表示されている整数を 8 に変化させることができます。

2 番目のテストケースでは、ボタンを何回押してもディスプレイに表示されている整数は 0 のまま変わらないので、これを 1 に変化させることはできません。

問題文

パ研ランドには N 個のアトラクションがあり、1 から N までの番号がつけられています。

また、これらのアトラクションを結ぶ道が N - 1 本あり、 1 から N - 1 までの番号がつけられています。

道 i (1 \leq i \leq N - 1) はアトラクション A_i と アトラクション B_i を双方向に結んでいます。

さらに、パ研ランドのそれぞれの道には「楽しさ」という値が設定されていて、道 i (1 \leq i \leq N - 1) の楽しさは C_i です。

パ研ランドでのアトラクション間の移動も楽しみたい hiikunZ 君のために、すべてのアトラクション i (1 \leq i \leq N) について、次の問題を解いてください。

hiikunZ 君はアトラクション i から、アトラクション i とは異なるアトラクション j (i \neq j,1 \leq j \leq N) を 1 つ決め、アトラクション i から アトラクション j に道を通る回数が最小になるように移動しようと考えています。

アトラクション j を適切に選んだとき、hiikunZ 君が通る道の「楽しさ」の平均値を最大でいくつにできるかを求めてください。

ただし、答えは整数では表せない場合があるので、答えの小数点以下を切り捨てた値を出力してください。

制約

• 2 \leq N \leq 100000
• 1 \leq A_i,B_i \leq N (1 \leq i \leq N - 1)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N - 1)
• どのアトラクションからどのアトラクションへも、いくつかの道を通ることで移動することができる
• 入力はすべて整数

入力例 1

3
1 2 3
2 3 6

出力例 1

4
6
6

アトラクション 1 について考えます。

アトラクション 1 からアトラクション 2 に移動する場合、通る道の「楽しさ」の平均値は 3 です。

一方、アトラクション 1 からアトラクション 3 に移動する場合、通る道の「楽しさ」の平均値は \frac{3+6}{2}=4.5 になります。

そのため、 1 行目にはこれらの最大値である 4.5 の小数点以下を切り捨てた値である 4 を出力してください。