Codeforces Round #736 (Div. 2) ABCD Solutions (Java/C++)

A. Gregor and Cryptography

Solution:

If P is an even number, just output 2 and P, so that the remainder is both 0. If P is an odd number, just output 2 and P-1, so that the remainder is both 1.

Code:

Java

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

C++

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

B. Gregor and the Pawn Game

Solution:

If the pawns can go directly to the end, then these pawns have priority to go directly to the end.
Then consider the pawn that has to eat an opponent pawn to reach the end. Consider the remaining pawns from left to right, and give priority to the opponent's pawn on the left.

Code:

Java

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

C++

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

C. Web of Lies

Solution:

If a noble has at least one noble friend who is bigger than him, then the noble will be killed sooner or later. Because nobles smaller than this noble will definitely be killed, and the next one will be this noble.

Therefore, we only need to count how many nobles have friends who are bigger than themselves.

Code:

Java

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

C++

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

D. Integers Have Friends

Solution:

If there are $a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m$, then there must be $(a_{i+1} - a_i) \bmod m = (a_{i+2} - a_{i+1}) \bmod m = \ldots = (a_j - a_{j-1}) \bmod m = 0$.

Let $d_i=a_{i+1}-a_i$. And if we want to verify whether there is such m in the interval from i to j, we only need to verify whether $\gcd(d_i, d_{i+1}, \ldots, d_{j-1})$ is not 1.

So we naturally thought of using the line segment tree to maintain the interval GCD. Then get the longest interval by enumerating i and j.
When we enumerate j, we don't need to re-enumerate from i every time, we can continue to enumerate following j based on the j left by the previous i.

Code:

Java

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

C++

Submission #124880246 - Codeforces
Codeforces. Programming competitions and contests, programming community
DigitalOcean Referral Badge 蜀ICP备19018968号