Note: English version of the above editorial.

478A — Starting bid

To solve the problem, it is important to note that during the game, the number of coins on the table can not be changed. The total number of coins on the table after a successful bid, remains unchanged. Therefore, by dividing the total number of coins on the table by the number of players, can obtain an initial rate for each. If you divide without remainder impossible, such a result can not play. Should pay attention to the fact that the initial rate of each of the players must be different from zero, hence, zero can never be the answer.

478B — Random team

If you restate the problem in terms of graph theory, it can be formulated as follows: There is a graph consisting of n vertices and m connected components. Inside each connected component, each pair of vertices connected by an edge of the component. In other words, each connected component is a full mesh. What is the smallest and the largest number of edges which may contain such a graph? Consider the process of constructing a graph of n vertices and m connected components. To begin, assume that each of the m component contains a single peak. It remains to distribute the remaining n — m vertices so as to minimize or maximize the number of edges. Note that when adding a new vertex in the connected component of size k, the number of edges is increased by k (new vertex is connected to each of the existing one edge). Consequently, in order to minimize the number of ribs formed on each step required each time to enhance top component connected smallest size. If you act according to this strategy, after the distribution of vertices on the connected components appears component size and component size. Similarly, in order to maximize the number of edges in each step must be added to the next vertex in the component connectivity greatest dimension. If you act according to such a strategy, then a single connected component of size n — m + 1, the remaining connected components will consist of a single vertex. Knowing the number of connected components and their sizes, you can count the total number of edges. For a full mesh components consisting of k vertices, the number of edges equals. It should be remembered about the need to use a 64-bit data type to store the number of edges, which depends quadratically on the value of n.

478C — table decoration

Consider a situation where the value max (r, g, b) — min (r, g, b) ≤ 1, then obviously the answer is (r+g+b)/3. We can always decorate so many tables three balloons of different colors. Obviously, the remaining amount will be less than three balls, and hence can not be used to decorate the table anyway. All the remaining cases it makes sense to reduce to the previously discussed. If there is one color, such that the number of balls that color is greater than the total number of balls for the other two colors, it is advantageous to decorate a table with two balls of one color and the ball of the remaining colors, which is greater than presently. Further it is possible in many ways to group operations and to carry out more than one operation at a time. Another solution include the fact that the response is different from (r+g+b)/3, but only if max (r, g, b) ≥ 2 · (r + g + b — max (r, g, b)), in which case the response r + g + b — max (r, g, b). In this case, the balls of the two most rare flowers will end earlier than the balls of one the most popular, if you decorate each table with two balls of the most popular colors.

478D — Red and green towers

To begin, you will notice that in order to build a red-green tower height h requires h(h+1)/2 cubes. Therefore, the height of the resulting tower predetermined limits never exceeds 893. This height can be determined in advance, if it is assumed that all blocks of the same color. Try to prove it yourself. Further it is possible to solve the problem using dynamic programming. Let F (t, r) — the number of ways to gather the greatest height of the tower, if collected t upper floors remained untapped r red cubes. Among the arguments of the function are no amounts remain green cubes g — can be uniquely determined from the values ​​of t and r: g = g0 — (t(t+1)/2 — (r0-r)), where r0 and g0 — the initial number of red and green cubes, respectively. Well and further consideration should be given only two transitions: Build t + 1-th level of the red or green blocks: F (t, r) = F (t + 1, r — t) + F (t + 1, r). Obviously, the cache data in an array size of 893 × 2 × 105 — not the best idea. In such a case, you can count the value of the function for all values ​​of t from 0 to h, stored in memory, only the values ​​for the current value of t and the previous one, from which it will depend.

478E — Wavy number

To solve this problem, it was necessary to note that the numbers on the undulating range of from 0 to 107 is much smaller than 107. In this case, the problem can be solved using an approach meet-in-the-middle. That is separate to solve this problem for the first seven digits of the answer, and for the last seven digits of the answer. This will require the wavy separately generate all numbers in a range from 0 to 107, starting with the increase of two adjacent numbers and similar wavy numbers which begin with the decrease of two adjacent numbers. Then for each of the first half, we can calculate rl — its residue modulo n and then determine the appropriate amount of the second half, which should be equal to the remainder of the division rr = (n-rl)mod n.

For the problem was a limitation of time equal to 1.5 seconds. In fact, if we write the solution to the approach meet-in-the-middle optimally enough, then the solution will take much less time. The above author's implementation (8271836) can solve a similar problem for 1 ≤ n, k ≤ 1016 for about 2.5 seconds. Courtesy: Google Translate

look at Accepted codes, everything becomes clear.

Can you explain D in simpler terms. The English editorial is quite difficult to understand

Say given colors are (a,b,c) and a<=b<=c then if max(a,b,c) — min(a,b,c) <=1 that means

1) Either max(a,b,c) == min(a,b,c) => a = b = c and answer is a = (a+b+c)/3 2) Or (a,b,c) = (a, a, a+1) or (a, a+1, a+1), here total number of colors = 3a + 1 or 3a +2, hence total number of decorations can maximum be a which is (a+b+c)/3

Secondly consider the case where c > 2*(a+b), then it is clear that answer is (a+b) because we can create tables using (a, 0, 2a) + (0, b, 2b) number of decorations.

Editorial suggests that if a+b < c, then take (0, 1, 2) colors to create a decoration and continue, now we have (a, b-1, c-2), I didn't understand why would this lead to optimal strategy.

Say we know the answer for (a, b-1, c-2) which is (a+b-1+c-2)/3, now the answer for (a,b,c) will be (a+b-1+c-2)/3 + 1 which is (a+b+c)/3.

Now the only thing left is say we start at (x,x,x) or (x,x,x+1) or (x,x+1,x+1) can we reach (a,b,c) by just adding (1,1,1) or (0,1,2) or (0,2,1) or (1,0,2) or (1,2,0). If so since we know the answer for (x,x,x) which is x, and each step we add 1, we know the answer for (a,b,c) will be (a+b+c)/3.

Also what happens in the case when a+b>c? Can some one explain?

I found an interesting solution by Hasan0540 to check whether (a,b,c) can be used to form m decorations, but didn't understand

#include <stdio.h>
#includ <algorithm>
using namespace std;
typedef long long ll;
int v[3];
bool can(ll m){
    ll z[3] = { v[0], v[1], v[2] };
    ll done = min(z[2], z[1]+z[0]);
    done = min(done, m);
    z[2] -= done;
    ll take = min(z[1], done);
    z[1] -= take;
    z[0] -= done - take;
    sort(z, z + 3);
    ll rem = m - done;
    if (z[2]<rem || z[1]<rem)
        return false;
    return true;
}
int main()
{
    for (int i = 0; i < 3; ++i)
        scanf("%d", v + i);
    sort(v, v + 3);
    ll l = 0, r = ((ll)v[0] + v[1] + v[2]) / 3, m, res = 0;
    while (l <= r){
        m = (l + r) / 2;
        if (can(m)){
            l = m + 1;
            res = m;
        }else
            r = m - 1;
    }
    printf("%lld\n", res);
    return 0;
}

AkiLotus's solution describes a way of creating decorations, Not sure why this is the right way.

void ProSolve() {
	sort(a.begin(), a.end(), greater<i64>());
	while (a[1] > 0 && a[0] + a[1] + a[2] > 2) {
		//cout << a << endl;
		if (a[0] == a[2]) {ans += a[0]; break;}
		if (a[1] == a[2]) {
			i64 diff = min((a[0]-a[1])/3, a[1]);
			if (diff == 0) {ans += a[2]; break;}
			ans += 2 * diff; a[0] -= diff * 4; a[1] -= diff; a[2] -= diff;
			sort(a.begin(), a.end(), greater<i64>()); continue;
		}
		i64 diff = min(min(a[0]-a[1], a[1]), a[1]-a[2]);
		ans += diff; a[0] -= 2*diff; a[1] -= diff;
		if (a[1] > a[2]) {
			diff = (a[0]-a[2])/3; ans += 2*diff;
			a[0] -= 3*diff; a[1] -= 3*diff;
			if (a[0] - a[2] > 1) {
				ans++; a[0] -= 2; a[1]--;
			}
			else if (diff == 0) {ans += a[2]; break;}
		}
		sort(a.begin(), a.end(), greater<i64>());
	}
	cout << ans;
}

nice explanation bro...