# AtCoder Beginner Contest 148

Updated:

AtCoder Beginner Contest 148

• Review: 2020-06-10

# 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


Tags:

Categories: