## 問題文
縦 $H$ 行、横 $W$ 列のマス目で表される山があります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と書き、マス $(i, j)$ の標高は $A_{i,j}$ です。はじめ、どのマスにも雪は積もっていません。
これから $Q$ 日分の天気が順に与えられます。$k$ 日目の天気は次のいずれかです。
- タイプ1(雪):`1 r1 c1 r2 c2 S` の形式で与えられる。$r_1 \le i \le r_2$ かつ $c_1 \le j \le c_2$ を満たすすべてのマス $(i, j)$ の積雪が $S$ 増える。
- タイプ2(雨):`2 r c` の形式で与えられる。マス $(r, c)$ に大量の雨が降る。雨は、上下左右に隣接するマスのうち標高が今いるマス以下のマスへ流れることを繰り返す。マス $(r, c)$ 自身と、雨が流れ着くことのできるすべてのマスの積雪が $0$ になる。
$Q$ 日分の天気がすべて終わったあと、各マスに積もっている雪の量を求めてください。
## 制約
- $1 \le H, W \le 1000$
- $1 \le Q \le 2 \times 10^5$
- $0 \le A_{i,j} \le 10^9$
- 雪の天気について、$1\le r_1\le r_2\le H, 1\le c_1\le c_2\le W,1\le S\le10^9$
- 雨の天気について、$1\le r\le H,1\le c\le W$
- 入力はすべて整数
yura1685's Problems
## 問題文
ある王国の領土は、縦 $H$ 行、横 $W$ 列のグリッドで表されます。上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼びます。
各マスは陸地か海のどちらかです。$S_i$ の $j$ 文字目が `#` のときマス $(i, j)$ は陸地であり、`.` のとき海です。
陸地のマスからは、上下左右に隣接する陸地のマスへ移動できます。互いに移動し合える陸地のマス全体を、ひとつの **島** と呼びます。現在、王国には $K$ 個の島があります。
国王は、すべての島を合併してひとつの島にまとめる政策を打ち出しました。王国は次の 2 種類の工事を、好きな順番で何度でも行えます。
- 海のマスを 1 つ選んで埋め立て、陸地にする。
- 陸地のマスを 1 つ選んで掘削し、海にする。
工事は 1 回あたり費用が $1$ かかります。島の個数をちょうど $1$ 個にするために必要な費用の最小値を求めてください。
## 制約
- $1\le H, W$
- $H\times W \leq 10^4$
- $2 \leq K \leq 7$
- $H, W, K$ は整数
- $S_i$ は `#` と `.` からなる長さ $W$ の文字列
- 与えられるグリッドの島の個数は $K$ 個である
素数 $p,q,r$ に対し、$16^p+8^q+5^r$ が $3$ で割り切れる最大の回数を $f(p,q,r)$ で表します。このとき、$f(p,q,r)$ の最大値が存在するのでこの値を $M$ とします。$f(p,q,r)=M$ となる素数の組 $(p,q,r)$ すべてについて、$\dfrac{16^p+8^q+5^r}{3^M}$ の総和を解答してください。
正の整数 $n$ に対し、各位の偶数の和を $e(n)$、各位の奇数の和を $o(n)$ と表します。ただし、$n$ のどの桁にも偶数が現れない場合と奇数が現れない場合はそれぞれ $e(n)=0, o(n)=0$ とします。このとき、以下の値を求めてください。
$$\sum_{n=1}^{10^{1111}}e(n)o(n)$$
次の条件を全て満たす正の整数 $n$ としてありうる最小値を $m$ とします。
- $nk$ がある整数の $2$ 乗となるような最小の正の整数 $k$ は $2$ である。
- $nk$ がある整数の $3$ 乗となるような最小の正の整数 $k$ は $3$ である。
- $nk$ がある整数の $5$ 乗となるような最小の正の整数 $k$ は $5$ である。
$m$ の正の約数の個数を解答してください。
$1\le x\lt y\lt z\le 101$ を満たす整数の組 $(x, y, z)$ であって、$6$ つの整数
$$x^{y^z},x^{z^y},y^{z^x},y^{x^z},z^{x^y},z^{y^x}$$
が全て平方数となるようなものの個数を解答してください。ただし、$a^{b^c}=a^{(b^c)}$ です。
$2\times 100$ のマス目のうち $103$ マスを黒く塗る方法であって、どの辺を共有して隣り合う $2$ マスについてもそのうち少なくとも一方は黒色となるものは何通りありますか?ただし、回転や反転によって一致するものも区別します。
正の整数 $c$ に対し、次の等式を満たす最小の正の整数 $n$ を $f(c)$ とします。
$$\lfloor{10^c\sqrt{n}}\rfloor - 10^c\lfloor{\sqrt{n}}\rfloor = 10^c-1$$
このとき、$\displaystyle\prod_{c=1}^{100}(f(c)-10^c)$ の正の約数の個数を求めてください。ただし、実数 $x$ に対して $\lfloor x \rfloor$ で $x$ を超えない最大の整数を表します。
$x$ についての $4$ 次方程式
$$x^4-20x^3-x^2-200x+100=0$$
を満たす**実数** $x$ であって、最も大きいものを求めてください。
$xy$ 平面上の点 $(0, 0)$ から点 $(6, 6)$ まで、次の $2$ つの条件を満たしながら格子点上を移動する方法は何通りありますか?
- 格子点 $(x, y)$ にいるとき、次に移動できる格子点は $(x+1, y), (x, y+1)$ のいずれかである。
- $x$ 座標、$y$ 座標がともに奇数である点をちょうど $4$ 回通る。
$10$ 以上の正の整数 $n$ であって、$1199_{(n)}$ が $19_{(n)}$ で割り切れるものはいくつありますか?
$n$ を正の整数とします。座標平面において円 $x^2+(y-13)^2=12^2$ と放物線 $y=\dfrac{1}{n}x^2$ が相異なる $4$ つの共有点をもち、それらの共有点を結んでできる四角形の面積を $S(n)$ とすると $\sqrt{n}S(n)$ の値は整数になりました。このような全ての正の整数 $n$ について、$\sqrt{n}S(n)$ の総和を解答してください。
次の $10$ 次方程式の(重解を含む)解を $x=x_1, x_2, \cdots, x_{10}$ とします。
$$x^{10} + 2x^9 + 2^2x^8 + \cdots + 2^9x + 2^{10} = 1685x - 1$$
このとき、$x_1^{11}+x_2^{11}+\cdots+x_{10}^{11}$ の値は正の整数となるのでこの値を解答してください。
各面に $1$ より大きな実数が書かれた歪な $6$ 面体のサイコロがあり、以下の条件を満たしています。
- 各目が出る確率は、その目の逆数に等しい。
- 各目の総和は $100$ に等しい。
- 各目は等比数列をなす。
このとき、サイコロの各目の総積を求めてください。
まだ問題がありません。