Educational Codeforces Round #108 ABCD ​Solutions

A. Red and Blue Beans

Solution:

Take the minimum value of $r$ and $b$ as $min$ and the maximum value as $max$.

Then distribute them to $max-min$ packets. Each packet put only 1 red bean and 1 blue bean.

Then the rest of the $max$ is divided into each packet to see if there are packets more than $d$ beans.

Code:

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

B. The Cake Is a Lie

Solution:

The cost is fixed. The cost must be $n -1+(m -1)\times n$.

Code

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

C. Berland Regional

Solution:

Calculate the prefix sum of skill point of student at each university. Then directly solve it with brute force.

It will not get TLE. Because for each university, we can skip when the $k$ exceed the number of students.

Code:

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

D. Maximum Sum of Products

Solution:

It can be regarded as a DP problem, although its essence is brute force.

Define $base=\sum\limits_{i=1}^n a_i \cdot b_i$. Which is the sum without reverse anything.

We define $dp[i][j]$ to represent the sum after reversed $[i,j]$ from $a$. It's not hard to find that: $$dp[i][j]=a[i]\cdot b[j] + a[j]\cdot b[i] - (a[i]\cdot b[i] + a[j]\cdot b[j]) + dp[i+1][j-1] + base$$

Of course, $dp[i][i]=base$. And $dp[i][i+1]$ is quite easy to find out.

Code:

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