# Judge System Update Test Contest 202004

Updated:

Judge System Update Test Contest 202004

# 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)$.

Tags:

Categories: