# Language Test 202001

Updated:

Language Test 202001

# Solutions

## PracticeA - Welcome to AtCoder

Do as they indicate us to do.

## ABC086A - Product

Flush Odd if $(AB) \% 2 = 0$ or ‘Even’ otherwise.

## ABC081A - Placing Marbles

Count 1.

## ABC081B - Shift only

Let

$f(x) =$ how many times we can divide $x$ by $2$.

We can implement $f$ by shift operation. The answer is $\min _ {i \in N} f(A[i])$.

## ABC087B - Coins

Execute $3$-times loops.

## ABC083B - Some Sums

For all $1 \leq x \leq N$, we calculate the sum of each digit of $x$. We sum up suitable $x$.

## ABC088B - Card Game for Two

Simple greedy algorithm works.

## ABC085B - Kagami Mochi

The answer is the number of the unique elements of $d$. We can easily calculate it as follows.

  sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()), d.end());
cout << d.size() << endl;


## ABC085C - Otoshidama

We can solve it by brute-force method in $O(N^2)$-time. Let $i$, $j$ be the number of $10000$-yen, $5000$-yen, respectively. We use $k$ to denote the number of $1000$-yen. Of course $k = N - i - j$. We check whether $10000i + 5000j + 1000k = Y$ or not.

## ABC049C - 白昼夢 / Daydream

We reverse $S$ and each keyword. Then, we can use greedy algorithm.

## ABC086C - Traveling

First of all, we set the first state as $(0, 0, 0)$.

For each $i$, let $d$ be the $l ^ 1$ distance between $(x _ i, y _ i)$ and $(x _ {i + 1}, y _ {i + 1})$ and $T = t _ {i + 1} - t _ i$. We can take a trip on $i \to (i + 1)$ if and only if $d \geq T$ and $\lvert T - d \rvert \% 2 = 0$.

## L - Interactive Sorting

### Solution

We define bool query(int const& x, int const& y); by asking the query.

### Case 1

We can use std::sort. We use query as its third argument.

### Case 2

The idea is the same as above. We make our marge_sort and use query as its compare function. With the help of STL, we can easily implement as follows.

template <typename Iter, typename Comp>
void merge_sort(Iter begin, Iter end, Comp cmp)
{
int N{static_cast<int>(end - begin)};
if (N <= 1)
{
return;
}
auto mid{begin + N / 2};
merge_sort(begin, mid, cmp);
merge_sort(mid, end, cmp);
vector<typename Iter::value_type> temp(N);
merge(begin, mid, mid, end, temp.begin(), cmp);
copy(temp.begin(), temp.end(), begin);
}


Here we have assumed that Iter is a random access iterator. Using SFINAE, we can implement as follows.

template <typename Iter, typename Comp>
void merge_sort_impl(Iter begin, Iter end, Comp cmp, random_access_iterator_tag)
{
// same.
}

template <typename Iter, typename Comp>
void merge_sort(Iter begin, Iter end, Comp cmp)
{
merge_sort_impl(begin, end, cmp, typename std::iterator_traits<Iter>::iterator_category());
}


### Case 3

We can possess the whole space of the possibilities by next_permutation. Every time we determine the query, we choose the most powerful query. That’s all.

## M - モンスターテイマー

We are waiting for WJ

Tags:

Categories: