Language Test 202001
Updated:
Source codes
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…