Sumitomo Mitsui Trust Bank Programming Contest 2019
Updated:
Source codes
Solutions
A - November 30
Determine whether the month-numbers are same or different.
B - Tax Rate
Just try all possibilities.
C - 100 to 105
This is done by a simple DP. But we can determine the answer by direct calculus and brute-force method.
Suppose that we use $N$ coins. Then, we can generate all the prices $[100N, 100N + 5N]$. We try all $1 \leq N \leq X / 100$.
D - Lucky PIN
We try all the possible PINs. We can generate the PIN if and only if the PIN is a subsequence of the original string. We define vector<vector<int>> V(10); as the places of the symbols. We define auto search = [&](int n, int x) {}; which returns the minimum number in $V[n]$ greater than or equal to $x$; if there is none, return $N$ instead. This is done by binary search. Then, the PIN $ijk$ can be generated if and only if search(k, search(j, search(i, 0) + 1) + 1) < N;
E - Colorful Hats 2
Solution
For example we consider the case $A = \{ 0, 0, 1, 0, 1, 1, 2 \}$. We possess the state as the triple of the children whose hat are the same instead of the triples of the children whose hat are red, green or blue. Let’s start by $A[0] = 0$ with $(0, 0, 0)$. We have three possibilities and the result is $(1, 0, 0)$. Then we see $A[1] = 0$ with $(1, 0, 0)$. We have two possibilities and the result is $(1, 1, 0)$. Then $A[2] = 1$ with $(1, 1, 0) \mapsto (2, 1, 0)$. The latter is the same. Then, we can count the $3 \cdot 2 \cdot 2 \cdot 1 \cdot 2 \cdot 1 \cdot 3$.
Similar problem
F - Interval Running
Solution
Let $X = (A _ 0 - B _ 0) T _ 0$ and $Y = (A _ 1 - B _ 1) T _ 1$. If $X < 0$, let $X \gets -X$ and $Y \gets -Y$. We consider the intermediate value theorem. We think of the the graph which connect $(0, 0)$, $(1, X)$, $(2, X + Y)$, $(3, 2X + Y)$, $\dots$. The answer is how many times the graph crosses the $x$-axis.
As we set just now, we can assume that $X > 0$. If $X + Y > 0$, the answer is $0$. If $X + Y = 0$, the answer is $\infty$. If $X + Y < 0$, the answer will be finite. Hereinafter we assume that $X + Y < 0$.
We see that for $(2n, n(X + Y))$, the $y$-coordinate $n(x + Y)$ is less than $0$. Therefore the number of the crossing point will be related to the $y$-coordinate of $(2n - 1, X + (n - 1)(X + Y))$. More precisely, the answer is \[ 2 \sharp \{ n \in \mathbb{N} \mid X + (n - 1)(X + Y) < 0 \} + \sharp \{ n \in \mathbb{N} \mid X + (n - 1)(X + Y) = 0 \} \]
Let $Z = \lvert X + Y \rvert$. The answer is
\[
A = \begin{cases}
\displaystyle 2 \cdot \frac{X}{Z} & (X \% Z \neq 0), \\
\displaystyle 2 \cdot \frac{X}{Z} + 1 & (X \% Z = 0).
\end{cases}
\]