Educational Codeforces Round 112 ABCDE Solutions (Java/C++)

A. PizzaForces

Solution:

It is not difficult to find that each slice takes 2.5 minutes on average. At the same time, we found that all even numbers over 6 can be constructed. So, for even numbers, we can just multiply by 2.5; for odd numbers, add one and then multiply by 2.5.

Code:

Java

C++

B. Two Tables

Solution:

Obviously, the green table will definitely be placed in the four corners, just enumerate the four corners.

Code:

Java

C++

C. Coin Rows

Solution:

We can find that for Bob, either all go up (blue) or all down (green). Otherwise, it must not be the best solution for Bob. So only need to enumerate the position where Alice's turn direction, and then quickly calculate Bob's score by prefix.

Code:

Java

C++

D. Say No to Palindromes

Solution:

It is not difficult to find that the substring must be a repetition of a certain arrangement of the three letters abc, so as to ensure that all substrings are not palindrome strings. Such as bacbacbac...

So we pre-calculate the prefix sum of the operands that need to be modified for all 6 permutations. For each query, we traverse 6 possibilities, and then calculate the total number of characters that need to be changed based on the prefix and sum.

Code:

Java

C++

E. Boring Segments

The key point is: the result only related to the maximum and minimum value of w. Therefore, after considering sorting by w, select a minimum range so that the 1-m path can be just completed.