Panasonic Programming Contest 2020
Updated:
Source codes
Solutions
A - Kth Term
Use array.
B - Bishop
Solution
Lemma B.1: The points $(i, j)$ with $i + j = 1$ in $\mathbb{Z}/2\mathbb{Z}$ are never reached.
Proof: By argument on equivalence class.
Lemma B.2: If $H, W \geq 2$, the points $(i, j)$ with $i + j = 0$ in $\mathbb{Z}/2\mathbb{Z}$ are reached.
Proof: By mathematical induction for the column number.
Obviously, if $H = 1$ or $W = 1$, the answer is $1$.
C - Sqrt Inequality
Solution
Since $a, b, c \approx 10 ^ 9$, we should avoid double.
\[
\begin{align}
\sqrt{a} + \sqrt{b} < \sqrt{c} &\Longleftrightarrow (\sqrt{a} + \sqrt{b}) ^ 2 < c \\
&\Longleftrightarrow a + b + 2 \sqrt{ab} < c \\
&\Longleftrightarrow 2 \sqrt{ab} < c - a - b \\
&\Longleftrightarrow c - a - b > 0 \land 4ab < (c - a - b) ^ 2.
\end{align}
\]
D - String Equivalence
Solution
A string $S$ is in normal form if and only if the followings hold.
- $S[0] =$
'a', - For any $i \in \lvert S \rvert$, $S[i] \leq \max _ {k \in i} S[k] + 1$.
Thus all the strings in normal form will be flushed by DFS.