Educational Codeforces Round 114 ABCD Solutions (Java/C++)

A. Regular Bracket Sequences

Solution:

Taking n=5 as an example, we can write 1 solution at once: ()()()()().

Then we can write the following 4 solutions:
(())()()()()
()(())()()()
()()(())()()
()()()()(())

Code:

Java

C++

B. Combinatorics Homework

Solution:

Obviously, we can find the maximum and minimum values of m. And we can get any m between the largest and smallest values by changing the order.

Consider the maximum value of m: it is not difficult to find that m is the maximum when we arrange it in aaaabbbbcccc. Therefore, the maximum value of m is a-1+b-1+c-1.

Then consider the minimum value of m: let's assume that the number of a is the largest. Then it is not difficult to find that m is the smallest when arranged in ababacacaaaa, so the smallest value of m is a-b-c-1.

Code:

java

C++

C. Slay the Dragon

Solution:

We found that, whether it is attack or defense, both actions are accomplished by the strength of heroes.

Therefore, it is not difficult to think that the optimal solution should avoid the overflow of defensive force or attack force as much as possible. For example, when the attack power overflows too much, it may be necessary to spend more gold coins to supplement the defense power accordingly.

So we only need to find the two heroes whose power is closest to x according to x and calculate the corresponding cost to the minimum value.

Code:

Java

C++

D. The Strongest Build

Solution:

Because m is only $10^5$ at most, it is ok to directly enumerate the first $10^5$ possibilities.

We use a priority queue to maintain various build, placing the highest strength first. We first add the greatest possible build to the queue. Then if the build of the head of queue is banned, add the n smaller builds corresponding to this build to the queue.

In this way, you can get the answer at most ban $10^5$ times.

Code:

Java

C++