AtCoder Beginner Contest 148
Updated:
- Review: 2020-06-10
Source codes
Solutions
A - Round One
Flush $6 - A - B$.
B - Strings with the Same Length
Just do as they indicate us to.
C - Snack
Flush $\mathrm{lcm}(A, B)$.
D - Brick Break
We can compute the maximum of the remaining bricks by greedy algorithm.
E - Double Factorial
Solution
Let
$g(n, p) = $ how many times $n$ can be divided by $p$.
The answer is
\[
g(n!!, 10) = \min(g(n!!, 2), g(n!!, 5)).
\]
If $n$ is odd, it immediately follows that $g(n!!, 2) = 0$. Hence the answer is zero. Hereinafter we assume that $n$ is even. We see that
\[
\begin{align}
n!! &= n \cdot (n - 2) \cdot \dots \cdot 4 \cdot 2, \\
\frac{n}{2}! &= \frac{n}{2} \cdot \left( \frac{n}{2} - 1 \right) \cdot \dots \cdot 2 \cdot 1.
\end{align}
\]
Therefore we see that
\[
\begin{align}
g(n!!, 2) &= g\left( \frac{n}{2}!, 2 \right) + \frac{n}{2}, \\
g(n!!, 5) &= g\left( \frac{n}{2}!, 5 \right).
\end{align}
\]
In addition, it follows that
\[
g(n!, p) = \frac{n}{p} + g\left( \frac{n}{p}!, p \right) + \frac{n}{p}.
\]
And it stops by $g(0, p) = 0$.
Another Solution
Just count how many $5$s $N!!$ has as factors. This is done directly as follows.
if (N & 1)
{
cout << 0 << endl;
return 0;
}
ll M{N};
ll five{0};
while (M >= 5)
{
five += M / 10;
M /= 5;
}
cout << five << endl;
F - Playing Tag on Tree
Solution
First of all, Takahashi-kun and Aoki-kun can’t pass each other. Therefore, Takahashi-kun cannot reach the vertex $x$ where $\mathrm{dist} _ T(x) \geq \mathrm{dist} _ A (x)$. Of course the vertexes on Aoki-kun’s side won’t be reached by Takahashi-kun. Otherwise, let $y$ be the intersection point of Takahashi and Aoki on the pass from the initial vertexes. We have $\mathrm{dist} _ T(y) \geq \mathrm{dist} _ A (y)$, which means Aoki-kun can capture Takahashi-kun as long as he wants to reach $x$. On the contrary, Takahashi-kun can reach $x$ where $\mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)$.
In addition, we see that, if Takahashi-kun reaches $x$, Aoki-kun will take $\mathrm{dist} _ A (x) - 1$ turns to capture him. Note that $-1$ means that Takahashi-kun will be captured in front of $x$. Therefore we can achieve \[ \max _ {x \colon \mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)} \mathrm{dist} _ A (x) - 1. \] In addition, this is the maximum value since Aoki-kun cannot reach each vertex $x$ by less than $\mathrm{dist} _ A (x)$ turns.
Others
Review 2020-06-10:
Assignments:
A - sample: 2, tle: 2.000, time: 02:12, from_submit: 21:36
B - sample: 3, tle: 2.000, time: 01:02, from_submit: 20:33
C - sample: 3, tle: 2.000, time: 00:42, from_submit: 19:52
D - sample: 4, tle: 2.000, time: 04:15, from_submit: 15:36
E - sample: 3, tle: 2.000, time: 05:14, from_submit: 10:23
F - sample: 4, tle: 2.000, time: 10:23, from_submit: 00:00