Judge System Update Test Contest 202004

Judge System Update Test Contest 202004

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - Walking Takahashi

The answer is as follows. \[ A = \begin{cases} S & L \leq S \leq R, \\
L & S \leq L, \\
R & \text{otherwise}. \end{cases} \]

You can use std::clamp.

int main()
{
  int S, L, R;
  cin >> S >> L >> R;
  cout << clamp(S, L, R) << endl;
}

B - Picking Balls

Just sort as they indicate us to. You can use structured binding.

C - Numbering Blocks

We write the numbers in the ascending order. Then, using DFS is suffice.

  void dfs(int a, int b, int c, int N)
  {
    if (!(a <= A && b <= B && c <= C))
    {
      return;
    }
    if (!(a >= b && b >= c))
    {
      return;
    }
    if (N == 0)
    {
      ++cnt;
      return;
    }
    dfs(a + 1, b, c, N - 1);
    dfs(a, b + 1, c, N - 1);
    dfs(a, b, c + 1, N - 1);
  }

D - Calculating GCD

Solution

First of all, we define \[ B _ i = \gcd(A _ 0, A _ 1, \dots, A _ i). \] This is calculated in $O(N)$-time for all $i \in N$. Here we have regarded the calculation of $\gcd$ pays the constant time.

Then, we see that, if there exists $j$ so that $\gcd(B _ j, X) = 1$, it holds that $\gcd(B _ i, X) = 1$ for all $i \geq j$. Thus we can use binary search.

The total time complexity is $O(N + Q \log N)$.

Others