PROBLEM LINK:
Practice
Author: (codechefnitj | CodeChef User Profile for Codechef NITJ Chapter | CodeChef)
Editorialist: Amritdeep Singh
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
In the above problem we have to find the number of operations required to make three numbers in Arithmetic Progression. In one operation we can add 1 to any of the three numbers.
EXPLANATION:
For three numbers a,b,c in A.P they follow the equation a+c=2b. So now according to the we will have mainly three cases
- A1+A3=2*A2
- A1+A3<2*A2
- A1+A3>2*A2
For the first case the numbers are already in A.P so the answer will 0.
For the second case, let us assume we do in total x operations on min(A1,A2) so now
A1+A3+x=2*A2:
x=2*A2-A1-A3
For the third case, we will have two subcases i.e. whether A1+A3 is even or odd. If A1,A2,A3 are in A.P then A1+A3 will should be even. So one operation would be needed to make A1+A3 even after that let us assume another x operations are done on A2:
A2+x=(A1+A3+1)/2
x=(A1+A3+1)/2-A2
So, total operations would be x+1. Incases the sum is even then number of operations would directly be:
x=(A1+A3)/2-A2
TIME COMPLEXITY:
O(1)
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define And &&
#define Or ||
#define space
#define int long long
#define vi vector<int>
#define pb(n) push_back(n)
#define mii map<int, int>
#define test_cases_loop \
int t; \
cin >> t; \
while (t--)
#define FIO \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define loop(var, initial, final) for (int var = initial; var < final; var++)
int32_t main()
{
FIO int a, b, c;
cin >> a >> b >> c;
int x;
if (a + c < 2 * b)
x = 2 * b - (a + c);
else{
if ((a + c) % 2){//a+c odd
x = ((a + c + 1) / 2 - b);
x++;
}
else
x = (a + c) / 2 - b;
}
cout << x << endl;
return 0;
}