Codeforces Round #747 ABCDEF Solutions (Java/C++)

A. Consecutive Sum Riddle

Solution:

Obviously $\frac {(l+r)\cdot (r-l+1)} 2 = n$, so $(l+r)\cdot (r-l+1) = 2\cdot n$.

We try to assume r-l+1=2, so we find that the above equation can be simplified to $(l + l + 1) \cdot 2 = 2 \cdot n$, which is $2\cdot l+1=n $.
At this time, as long as n is an odd number, l has a solution.

So now there is only the case where n is an even number. At this point, we try to assume r-l+1=4. So the original equation can be simplified to: $(2\cdot l + 3) \cdot 4 = 2 \cdot n$. So $(2\cdot l + 3) = \frac n 2$.
At this time, as long as $\frac n 2$ is an odd number, l has a solution.

So we are left with the situation where n is divisible by 4. In the same way, let's double r-l+1 again. This goes back and forth until $2l+?$ is equal to an odd number.

Code:

Java

C++

B. Special Numbers

Solution:

Obviously, considering the n-ary form of the final number, this n-ary number must only contain 0 or 1. Since it is 0 or 1, then naturally, the k-th largest number is the binary form of k.

For example, k=4, the binary form of k is $(100)_2$. Then the n-base number is $(100)_n$.

Code:

Java

C++

C. Make Them Equal

Solution:

First of all, it can be immediately discovered that the number of operations must not exceed 2. Because n and n-1 must be able to replace all characters with c.

Then we look from the back to the front and find the i on the far right such that s[i]=c. If $i*2-1\geq n$, then through this i, all characters except s[i] can be replaced with c, but it happens that s[i]=c, so only one operation is required.
And if $i*2-1<n$, if we do an operation on i, then s[2i] must not be equal to c (otherwise, according to the definition of i, i should actually be 2i). Therefore, a second operation must be required. It is better to use n and n-1 directly, which is easier.

Code:

Java

C++

D. The Number of Imposters

Solution:

We assume the role of one of them, and then use DFS to deduce the roles of the others based on the comments related to him.

It should be noted that when we change our assumptions about one person's role, the corresponding roles of all other people will be directly opposite to the previous deduction. Therefore, we only need DFS once.

Code:

Java

C++

E. Rubik's Cube Coloring (easy/hard version)

Solution:

We divide colors into 3 categories: white and yellow are the 0th category, green and blue are the 1st category, and red and orange are the 2nd category.

We first consider easy version. We will consider the number of possibilities for each category of color in current node from the bottom, as shown in the following figure:

First, we consider the node in the bottom. Obviously, there are actually two choices for each category.
Then we consider the second layer, taking category 0 as an example. Obviously, if a node in the second layer chooses a color of category 0, then neither of the left and right children of this node can be the color of category 0. Also note that the 0th category have two colors. So there are (left[1]+left[2])*(right[1]+right[2])2=(2+2)(2+2)*2=32 kinds of painting methods.
Similarly, we can build from the bottom up to the root of the tree.

And notice that if there is no pre-painting, we find that the nodes of each layer are exactly the same. At the same time, each type is the same in the node. So we can directly use a one-dimensional array to calculate it.

For the hard version, since there are up to 2000 nodes with pre-painted colors. We build these nodes and all their parent nodes separately. Because the depth is at most 60, there are at most 2000*60=120000 nodes to be constructed separately.
Similarly, we can build from the bottom up. The difference with the easy version is that in the hard version, we need to build a separate node from bottom to top based on the result of the easy version.

Code:

Java

C++

F. Ideal Farm

Solution:

First, if k is greater than s, then it must be no. Because in any case, there will be no lucky situation. Then if k is equal to s, then it must be yes. Because in any case, you can choose all pens to achieve lucky.

Therefore, we only need to consider the case where s is greater than k. Obviously, we only need to find out under what situation that we can construct an unlucky distribution method.

It is not difficult to find this structure$$\underbrace{1, 1, 1, \dots}{k-1},\ k+1,\ \underbrace{1,1,1,\dots}{k-1 },\ k+1,\ \dots$$ That is, first, each pen is assigned 1 animal, and then every k-1 pen is assigned k more animals.

If s is not enough to support the above structure, then you need to reduce the value from a certain k+1 above. (Because the pen cannot be empty, it cannot be subtracted from 1.)
Therefore, we only need to consider how many animals are needed for this construction, so when $s-n<\lfloor \frac{n}{k}\rfloor k$, unlukcy cannot be constructed, and Yes is output.

Code:

Java

C++