Codeforces Round #750 ABCDE Solutions (Java/C++)

A. Luntik and Concerts

It's easy to guess the result: just look at the parity of the total time. But the proof of this topic is still a bit interesting.

Codeforces Round #750 Luntik and Concerts Solution (Java/C++)
Solution:Let me show the conclusion first. The conclusion is that if the total time is an even number, output 0, otherwise output 1.
Click the link above for detail solution

B. Luntik and Subsequences

Solution:

Just count the number of 0 and 1, denoted as c0 and c1, respectively. The final answer is $c1\cdot 2^{c0}$.

Code:

Java

Submission #133165381 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #133165449 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Grandma Capa Knits a Scarf

Solution:

Enumerate the chosen letters by brute force.

Code:

Java

Submission #133167722 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #133167910 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Vupsen, Pupsen and 0

Solution:

First of all, it is not difficult to find that we must be able to find a structure such that $|\sum_{i=1}^n(-1)^?\cdot a[i]|\leq 10000$, where the value of ? is based on the method to construct it.
In fact, for any j, $|\sum_{i=1}^j(-1)^?\cdot a[i]|\leq 10000$ can be easily constructed.

We denote $\sum_{i=2}^j(-1)^?\cdot a[i]$ as sum (note that i here starts from 2). So obviously $|sum|\cdot a[1]\pm |a[1]|\cdot sum=0$. So it is obvious that there is such a way to construct:$$b[i]=\begin{cases}
(-1)^?\cdot |sum|,  & \text{if $i=1$} \\[2ex]
(-1)^?\cdot |a[1]|,  & \text{if $i\neq 1$}
\end{cases}
$$The value of ? can be selected according to the situation.

But there are two problems here:

  1. The value of sum is 0. In this case, we arbitrarily reverse the sign of any digit.
  2. According to the above operation, the maximum value of sum will become 20000. Therefore, the final result needs to be divided by the greatest common divisor of a[1] and sum as the final result.

Code:

Java

Submission #133171555 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #133171773 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Pchelyonok and Segments

A DP problem. The key is to find that in fact [l1, r1] is only related to [l2, r2], and further [l2, r2] is only related to [l3, r3], and so on.

Codeforces Round #750 Pchelyonok and Segments Solution (Java/C++)
Solution:Let’s take k=3, n=10 as an example, consider the choice of [l1, r1], consider the following two choices: [4, 6] and [3, 5].
Click the link above for detail solution

Show Comments
DigitalOcean Referral Badge