Educational Codeforces Round 109 ABCDE Solutions

A. Potion-making

Solution:

It is a fractional simplification of $ \frac k {100} $. The simplified denominator is the answer.

Code:

C++

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

Java

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

B. Permutation Sort

Solution:

First, if it is already in ascending order, then print 0.

If the first number is 1 or the last number is n, then only need 1 step to do it.

If the first number is n and the last number is 1, then it needs 3 steps:
1. move 1 or n from the ends to the center.
2. put the first number to 1 or last number to n.
3. put others in ascending order.

Otherwise, we can skip the first step above. So only need 3 steps.

Code:

Java

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

C++

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

C. Robot Collisions

The solution of this problem is to go from right to left and try to find robots which is moving left to match.
If cannot find, then convert current robot to the robot which is moving left. And match it with following robots.

Educational Codeforces Round 109 Robot Collisions Solution (Java/C++)
SolutionFirst, for any two robots $i$ and $j$, if $x_i\equiv x_j\mod 2$ (the remainder of 2 is same), then this two robots must meet and explode
Click here for more details

D. Armchairs

Cannot find the greedy solution. The DP is easier. We just need get the minimum cost when we move i-th 1 to j-th 0.

Educational Codeforces Round 109 Armchairs Solution (Java/C++)
Solution:Define dp[i][j] to stand for the minimum cost if we move the people from the i th occupied armchair to j-th empty armchair.
Click here for more details

E. Assimilation IV

It is a simple problem with reverse thinking plus basic number theory.

Educational Codeforces Round 109 Assimilation IV Solution(Java/C++)
Solution:To get the expected number, we need calculate the total number of points can be conquered in all permutation.
Show Comments
DigitalOcean Referral Badge