Sumitomo Mitsui Trust Bank Programming Contest 2019

Updated:

三井住友信託銀行プログラミングコンテスト2019

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} \]

Others