Codeforces Round #718 ABCDE Solutions

A. Sum of 2050

Solution:

Obviously $n$ must be divisible by 2050. Then every decimal digit of $\frac n {2050}$ should be composed of the corresponding $10^k$. So just find the sum of each digit of $\frac n {2050}$.

Code:

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

B. Morning Jogging

Solution:

Obviously, Sort all the roads. Assign the first $m$ roads to the $m$ individuals in turn. The order of other roads doesn't matter.

Code:

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

Tips for implementation:

It is very common to sort all edges by length. But the hard thing is we need to put the roads back with some roads are already assigned to someone.

A personal way of implementation is: after assigned first $m$ roads. I sort the road by the index of checkpoints and index of the road again.


C. Fillomino 2

Solution:

Refer to the figure below, because the red part has been used up, the blue on the left of the red is the value of the upper one, and the green on the right of the red is the value of the right.

In the same way, the second time is when the number of times of 2 is exhausted, the same method can build the next layer.

Code:

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

D. Explorer Space

Just a normal DP problem.

Codeforces Round #718 Explorer Space - DP
Solution:First of all, if $k$ is not an even number, there must be no answer.Define $map[i][j][d]$ (where $0 \leq d <4$) represents the side length of $(i,j)$ in four directions.

E. Group Photo

Just a simple binary search problem. But there are lots of different cases that have to be considered. So more a implementation question.

Codeforces Round #718 Group Photo - Binary Search
Solution:First of all, Base on ci−ci−1≤ci+1−ci and pi−pi−1≥pi+1−pi we can roughly found that:
Show Comments
DigitalOcean Referral Badge