Hello everyone. I have noticed the absence of round 273's editorial, so I decided to write one. This is the first time I write an editorial, so hope everyone like this!

I didn't know how to solve C and E yet, so it would be appreciated if someone help me with these problems.

Also, how to use LaTex in codeforces? I want to use this so my editorial would be more clear to read.

**UDP:** Actually, there's a (well-hidden) tutorial for this round, but it's written in Russian (with a English version using google translate in comment section). If you can read Russian, click here.

**UDP2:** Problem C is now available!

# A — Initial Bet

Since the coin only pass from this player to other player, the coins sum of all player won’t change in the game. That mean, we’ll have `5*b = c1+c2+c3+c4+c5`

. We’ll put `sum = c1+c2+c3+c4+c5`

. So, if `sum is divisible by b`

, the answer will be `sum/b`

. Otherwise, the answer doesn’t exist.

Be careful with the case `0 0 0 0 0`

too, since `b > 0`

, answer doesn’t exist in this case.

**My solution:** 11607374

*Complexity: O(1)*

# B — Random Teams

If a team have `a`

participants, there will be `a*(a-1)/2`

pairs of friends formed.

For the minimum case, the participants should be unionly – distributed in all the team. More precisely, each team should not have more than one contestant compared to other team. Suppose we’ve already had `n div m`

contestant in each team, we’ll have `n mod m`

contestant left, we now should give each contestant left in first `n mod m`

teams.

For example, with the test `8 3`

, we’ll first give all team 8 div 3 = 2 contestants, the result now is `2 2 2`

. We’ll have 8 mod 3 = 2 contestants left, we should each contestant in the first and the second team, so the final result is: `3 3 2`

.

The maximum case is more simple, we should give only give one contestant in first `m-1`

teams, and give the last team all the contestant left. For example with above test, the result is `1 1 6`

.

Since number of the contestant in one team can be 10^9, the maximum numbers of pairs formed can be 10^18, so we should use `int64`

(`long long`

in c++) to avoid overflow.

**My solution:** 11607784

*Complexity: O(1)*

# C — Table Decorations

spiderbatman has a great idea for this problem. You can read his comment here.

The order of the balloons isn't important, so instead or `r`

, `g`

, `b`

, we'll call them `a[0]`

, `a[1]`

, `a[2]`

and sort them in ascending order. We'll now have `a[0] <= a[1] <= a[2]`

.

There's two case:

`2*(a[0]+a[1]) <= a[2]`

. In this case, we can take`a[0]`

sets of`(1, 0, 2)`

and`a[1]`

sets of`(0, 1, 2)`

, so the answer is`a[0]+a[1]`

.`2*(a[0]+a[1]) > a[2]`

. In this case, we can continuously take a set of two balloon from`a[2]`

and a balloon from`max(a[0], a[1])`

until a point that`a[2] <= max(a[0], a[1])`

. At this point,`max(a[0], a[1])-a[2] <= 1`

, and since`max(a[0], a[1]) - min(a[0], a[1]) <= 1`

too,`max(a[0], a[1], a[2]) - min(a[0], a[1], a[2]) <= 1`

. All we have to do left is take all possible`(1, 1, 1)`

group left. Since we only take the balloons in group of 3,`(a[0]+a[1]+a[2]) mod 3`

doesn't change, so there will be at most`(a[0]+a[1]+a[2]) mod 3`

balloons wasted. We go back to the beginning now. The answer is`(a[0]+a[1]+a[2]) div 3`

.

**My solution:** 11614150

*Complexity: O(1)*

# D — Red-Green Towers

For more convenient, we’ll call a function `trinum(x) = (x*(x+1))/ 2`

, which is also the number of blocks needed to build a tower with height `x`

.

First, we’ll find h, the maximum height possible of the tower. We know that `h <= trinum(l+r)`

. Since `(l+r) <= 2*10^5`

, `h <= 631`

, so we can just use a brute-force to find this value.

Now, the main part of this problem, which can be solved by using dynamic programming. We’ll `f[ih, ir]`

the number of towers that have height `ih`

, can be built from `ir`

red block and `trinum(ih)-ir`

green blocks.

For each `f[ih, ir]`

, there’s two way to reach it:

Add

`ih`

red block. This can only be done if`ih <= ir <= min(r, trinum(ih))`

. In this case,`f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`

.Add

`ih`

green block. This can only be done if`max(0, trinum(ih)-g) <= ir <= min(r, trinum(ih-1))`

. In this case,`f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih]`

.

The answer to this problem is sum of all `f[h, ir]`

with `0 <= ir <= r`

.

We will probably get MLE now...

**MLE solution:** 11600887

How to improve the memory used? We'll see that all `f[ih]`

can only be affected by `f[ih-1]`

, so we'll used two one-dimension arrays to store the result instead of a two-dimension array. The solution should get accepted now.

**Accepted solution:** 11600930

*Complexity: O(r*sqrt(l+r))*

# E — Wavy numbers

Unfinished...