Problem Name: Maximum Operations. Read the description for more Info

Problem Statement
You are given three numbers a, b, c. You can subtract 1 from any two of the provided three numbers. Your task is to determine the maximum number of operations such that after performing all the operations optimally, all three numbers are non-negative.

Input Format

  • The first line contains T denoting the number of test cases.
  • For each test case, the next line contains three space-separated integers a, b, c respectively.

Output Format
For each test case print the maximum number of operations in the new line.

Constraints
1 \leq T \leq 100
1 \leq a, b, c \leq 10^{18}

Sample Input

2
2 3 4
1 2 5

Sample Ouput

4  
3 

Can you tell me how to solve the problem, as the constraints are high for a, b, c, means there would a closed-form formula to solve it.
Please if its possible, can you give me a step-by-step editorial like explanation about how you arrive at the solution.

@everule1 @ssjgz

P.S. The problem statement is not from any ongoing contest.

1 Like
2 Likes

@ssjgz I know the answer is min((a+b+c)/2, a+b) but I have difficultly arriving at answer? Can you give me as logical explanation about the solution?

Assume a<=b<=c without loss of generality.

If a +b<=c then answer is a+b.
Why?
Every time we do a move, we must remove one from either or a or b. So at most we can do a+b operations.
When a+b>c
Is it possible to reach 0,0,0 or 0,0,1 always?
Yes. That is because it’s like a triangle.

It’s a bit difficult to articulate, but the main thing is I can remove c from a and b such that the difference is at most 1. That is because we know a and b are less than c and therefore b-a is also less than c. So we can make sure that the difference doesn’t exceed 1, so we reach either 0,0,1 or 0,0,0 depending on the parity, and we can do (a+b+c)/2 moves.

2 Likes

@everule1 Thanks for the explanation.

we can do first short the number and get middle number and take it as temporary variable number and find difference between first and third number and add in the temporary variable and you get your answer

Consider a > b > c
And. q = a - b
p = b - c

Let a,b,c be no. of blocks piled on one another.
A MOVE is removeing 2 blocks 1 from any two(a,b)(b,c)(a,c)

Finally.

Ans = (5a - c) / 2

Independent of b ( middle ). a>b>c