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++

Java

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

C++

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.

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.

E. Assimilation IV

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