PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Soumyadeep Pal
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh
DIFFICULTY:
852
PREREQUISITES:
None
PROBLEM:
Chef has two integers X and Y. Chef wants to perform some operations to make X and Y equal. In one operation, Chef can either:
- set X := X + 1
- or set Y := Y + 2
Find the minimum number of operations required to make X and Y equal.
EXPLANATION:
There are two cases:
Case 1 X\leq Y: Since, Y cannot be decreased by any method, therefore X has to be increased by at least Y-X. Thus, this is the minimum number of operations and all operations are of type 1.
Case 2 X>Y: Y has to be made at least X. Therefore the minimum number of operations is ceil(\frac{(Y-X)}{2}). If X and Y don’t have the same parity then Y would be increased to X+1 by doing these operations and thus we need to do one more operation which is increasing X by 1.
\therefore answer = ((X\leq Y)?Y-X:\frac{(X-Y+1)}{2}+1- (X%2==Y%2))
TIME COMPLEXITY:
O(1) for each test case.
SOLUTION:
Setter's solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int x, y; cin >> x >> y;
if (y >= x) {
cout << (y - x) << '\n';
} else {
if (y % 2 == x % 2) {
cout << (x - y) / 2 << '\n';
} else {
cout << 2 + (x - y) / 2 << '\n';
}
}
}
return 0;
}
Editorialist's solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int x, y;
cin >> x >> y;
cout << ((x <= y) ? y - x : 1 - (x % 2 == y % 2) + (x - y + 1) / 2) << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}