C# – CodeForces – Okabe and Banana Trees

Posted on July 11, 2017 by

Vitosh Posted in C Sharp Tricks, CodeForces

It does not happen a lot, but this time the 2. problem of CodeForces really made me rethink my life choices and made me feel a bit sorry that I was in a school where we studied Maths about 4 hours per week. I mean, I had to literally stop and google linear equations and then read everything as if I have never seen it.

Anyhow, it was useful. This is the problem:

Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tree in such a point, and it has x + ybananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation $\text{[math]}$ . Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe’s rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 10¹⁸. You can trust him.

Input

The first line of input contains two space-separated integers m and b (1 ≤ m ≤ 1000, 1 ≤ b ≤ 10000).

Output

Print the maximum number of bananas Okabe can get from the trees he cuts.

My solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Startup
{
    static void Main()
    {
        long[] numbers = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long m = numbers[0];
        long b = numbers[1];
        long result = 0;
        long x = 0;

        for (long y = 0; y <= b; y++)
        {
            x = m*(b - y);
            result = Math.Max(result, (x + 1) * (y + 1) * (x + y)/2);
        }

        Console.WriteLine(result);

    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

class Startup

{

static void Main()

{

long[] numbers = Console.ReadLine().Split().Select(long.Parse).ToArray();

long m = numbers[0];

long b = numbers[1];

long result = 0;

long x = 0;

for (long y = 0; y <= b; y++)

{

x = m*(b - y);

result = Math.Max(result, (x + 1) * (y + 1) * (x + y)/2);

}

Console.WriteLine(result);

}

Explanation to the solution:

– not an easy solution, although it is just a few lines. First, you should remember what is X, Y, M and B in the formula $\text{[math]}$ . Google helps a lot there. 🙂

Pretty much B is the place where the line intercepts the Y of the coordinate system and M is the slope. That is why, if we loop from 0 to B, we would loop through each point of the line, where we may find bananas.

– second difficult part – come from y=-x/m+b to something that a C# compiler can easily calculate, if we need to find X. Thus, you should remember to multiply with M every part of the equation and then make it up to x = m*(b-y);

– third difficult part – do not count as an amateur, but find a nice formula, summing the bananas. This was a bit difficult, but after spending some 10 minutes with the two examples and brute-forcing it on a paper, it turned out to be (x+1)*(y+1)*(x+y)/2.

– last quite easy part – use long, not integer.

That’s all! The problem is definitely easy, if you have solved such problems before. If not, Uncle Google is there to help you! Cheers! 🙂

Tagged with: C#, codeforces, linear equations

C# – CodeForces – Okabe and Banana Trees

Related posts: