ABC460参加記

問題文
正整数 $N, M$ が与えられます。
$M$ の値が $0$ でない間以下の操作を繰り返すとき、操作を行う回数を求めてください。

• $N$ を $M$ で割った余りを $x$ とする。
• $M$ の値を $x$ で置き換える。

なお、この操作を有限回行うことにより $M=0$ になることが証明できます。

制約

• $1 \le N, M \le 1000$
• 入力される値はすべて整数

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

出力
答えを出力せよ。

問題文
$xy$ 平面上に 2 つの円 $C_1, C_2$ があります。ただし、本問題において円とは円周のことを指します。
円 $C_1$ は中心の座標が $(X_1, Y_1)$ で半径が $R_1$ です。
円 $C_2$ は中心の座標が $(X_2, Y_2)$ で半径が $R_2$ です。
円 $C_1$ と円 $C_2$ が共有点を持つかどうかを判定してください。言い換えると、点 $(X_1, Y_1)$ からの距離が $R_1$ であり、かつ点 $(X_2, Y_2)$ からの距離が $R_2$ であるような点が 1 個以上存在するかどうかを判定してください。

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

• $1 \le T \le 100$
• $0 \le X_1, Y_1, X_2, Y_2 \le 10^9$
• $1 \le R_1, R_2 \le 10^9$
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 番目のテストケースを意味する。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$

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

$X_1 \;\; Y_1 \;\; R_1 \;\; X_2 \;\; Y_2 \;\; R_2$

出力
$T$ 行出力せよ。
$i$ 行目には $i$ 番目のテストケースの答えを出力せよ。
各テストケースでは、円 $C_1$ と円 $C_2$ が共有点を持つ場合は Yes を、そうでない場合は No を出力せよ。

問題文
寿司の材料として、$N$ 個のシャリと $M$ 個のネタがあります。
$i$ 番目のシャリの重さは $A_i$、$j$ 番目のネタの重さは $B_j$ です。
あなたは、シャリとネタを組み合わせることで寿司を作ろうとしています。
寿司を $1$ つ作るためには、$1$ つのシャリと $1$ つのネタを組み合わせる必要があります。ただし、ネタの重さはシャリの重さの $2$ 倍以下でなければなりません。また、$1$ つのシャリやネタを複数の寿司に使うことはできません。
作ることのできる寿司の個数の最大値を求めてください。

制約

• $1 \le N, M \le 2 \times 10^5$
• $1 \le A_i, B_j \le 10^9$
• 入力される値はすべて整数

入力
入力は以下の形式で標準入力から与えられる。
$N \;\; M$
$A_1 \;\; A_2 \;\; \dots \;\; A_N$
$B_1 \;\; B_2 \;\; \dots \;\; B_M$

出力
答えを出力せよ。

問題文
$H$ 行 $W$ 列のマス目があります。このマス目の上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼びます。
すべてのマスは白または黒で塗られています。マス目の情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \dots, S_H$ によって与えられ、$S_i$ の $j$ 文字目が . のときマス $(i,j)$ は白で、$S_i$ の $j$ 文字目が # のときマス $(i,j)$ は黒で塗られています。
あなたは、以下の操作を $10^{100}$ 回行います。

すべてのマスに対して同時に以下の規則で色の塗り替えを行う。

• 操作前に白く塗られているマスは、そのマスに隣接する黒く塗られているマスが存在するとき、またそのときに限り黒く塗り替える。ただし、マス $(x,y)$ とマス $(x',y')$ が隣接しているとは、片方のマスがもう片方のマスの 8 近傍にある、すなわち $\max(|x-x'|, |y-y'|)=1$ であることを指す。
• 操作前に黒く塗られているマスは、白く塗り替える。

操作を終えた後に各マスが何色で塗られているか求めてください。

制約

• $1 \le H \times W \le 10^6$
• $H, W$ は正整数
• $S_i$ は .、# からなる長さ $W$ の文字列

入力
入力は以下の形式で標準入力から与えられる。
$H \;\; W$
$S_1$
$S_2$
$\vdots$
$S_H$

出力
$H$ 行出力せよ。
各行に .、# からなる長さ $W$ の文字列を $1$ つずつ出力せよ。
$i$ 行目の文字列の $j$ 文字目は $10^{100}$ 回の操作を行った後にマス $(i,j)$ が白で塗られているとき . に、黒で塗られているとき # になるようにせよ。

問題文
正整数 $a, b$ に対して、$a$ と $b$ を繋げて書いた時に出来る整数を $\text{concat}(a, b)$ と呼びます。厳密に述べると、$\text{concat}(a, b)$ を次のように定義します。

• $a, b$ を 10 進表記して出来る文字列を $A, B$ とする。
• $A, B$ をこの順に結合して出来る文字列を $C$ とする。
• $C$ を 10 進表記された整数とみなした時の値を $\text{concat}(a, b)$ とする。

例えば $a=123, b=45$ の時 $\text{concat}(a, b)=12345$ です。
正整数 $N, M$ が与えられます。
$N$ 以下の正整数の組 $(x, y)$ であって $\text{concat}(x, y) \equiv x+y \pmod M$ であるものの個数を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1 \le T \le 10^4$
• $1 \le N \le 10^{18}$
• $2 \le M \le 10^9$
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。ここで $case_i$ は $i$ 番目のテストケースを意味する。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$

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

$N \;\; M$

出力
$T$ 行出力せよ。
$i$ 行目には $i$ 番目のテストケースの答えを出力せよ。
各テストケースでは、条件を満たす $(x, y)$ の個数を $998244353$ で割った余りを出力せよ。