Educational Codeforces Round #106 ABCD Solutions

A. Domino on Windowsill

Solution:

Place the domino upright in vertical is fine. Then place in horizontal for the extra part.

Code:

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

B. Binary Removals

Solution:

Enumerate the position of the last 0. Then try to match the requirement. If all positions failed, then return "No".

There are two special cases:

  1. All numbers are 1. For this case, the position of last 0 should be -1.
  2. All numbers are 0. For this case, the position of last 0 should be $|s|$

Code:

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

C. Minimum Grid Path

Solution:

Because there is no difference in the direction of the first step. So we let the first step is to the right.

So we can find that: the even segments are to right, and odd segments are to up. It's greedy. The length of segments with minimal $c_i$ as longer as possible.

It can be seen as a DP problem. But after compress state, it not a really DP problem. $$dp[i]=(\sum_{j=0}^{i}c_j)+(\min\limits_{0<j<=i,j\%2=0}{c_j})\times{times_0}+(\min\limits_{0<j<=i,j\%2=1}{c_j})\times{times_1}$$
$times$ represent the remaining length after all the $c$ move only one step for the current direction. And assign this remaining length to the minimal $c$ to each direction.

Code:

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

D. The Number of Pairs

Solution:

First of all, we should know that: $lcm(a,b)=gcd(a,b)\times{f}$.

So immediately transform the original condition to get: $$c \cdot f \cdot gcd(a, b)-d \cdot gcd(a, b) = x$$

Of course $gcd(a,b)\neq 0$, So:$$c \cdot f - d = \frac x {gcd(a,b)}$$

It's very clear now.

Enumerate this $gcd(a,b)$. Calculate corresponding $f$. And base on the number of prime factors of $\frac f {gcd(a,b)}$ (Let's call it $count$). Now we can get the number of all possibilities, which is $2^{count}$.

Finally, it should be noted that this problem needs to preprocess out the $count$. Otherwise, will get TLE.

Code:

Submission #113424991 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge