Thanks…
My bad…
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t–) {
int a,b,x;
cin>>a>>b;
int arr[100];
for(x=min(a,b); x<=max(a,b) ;x++) {
int e = ceil((b-x)*0.5);
int m = ceil((x-a)*0.5);
arr[x] = e + m;
}
int maxx = arr[min(a,b)];
for(x=min(a,b); x<=max(a,b);x++) {
if (arr[x] > maxx)
maxx = arr[x];
}
cout<<maxx<<endl;
}
return 0;
}[quote=“vichitr, post:1, topic:92689, full:true”]
PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Vichitr Gandas
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic Maths
PROBLEM:
Given two integers A,B. You have to choose an integer X in the range [minimum(A,B), maximum(A,B)] such that ⌈\frac{B−X}{2}⌉+⌈\frac{X−A}{2}⌉ is maximum.
QUICK EXPLANATION
Try solving it for following 3 cases separately: 1) A=B, 2) A>B and 3) A<B.
EXPLANATION
Let’s divide the given problem in following three cases:
Case 1: A=B
In this case, we have only one choice for X that is X=A=B. In this case given sum is ⌈\frac{B−X}{2}⌉+⌈\frac{X−A}{2}⌉ = ⌈0⌉+⌈0⌉ = 0.
Case 2: A < B
Observation 1: Choose any X between the range [A, B], the given expression would always be either (B-A)/2 or (B-A)/2 + 1.
Observation 2: Its always possible to achieve the sum (B-A)/2+1 if A<B.
- Subcase (i): A-B is odd: in this case, by choosing X=A, we get the sum ⌈\frac{B−A}{2}⌉ = (B-A)/2 +1.
- Subcase (ii): A-B is even: in this case, by choosing X=A+1, we get the sum ⌈\frac{B−A-1}{2}⌉ +⌈\frac{A+1−A}{2}⌉= \frac{B-A}{2} +1 as ⌈\frac{1}{2}⌉ = 1.
Case 3: A > B
Lets solve it similar to the previous one.
- Subcase (i): A-B is odd, we get the sum (B-A)/2 for every X.
- Subcase (ii): A-B is even: in this case, by choosing X=A-1, we get the sum ⌈\frac{B−A+1}{2}⌉ +⌈\frac{A-1−A}{2}⌉= \frac{B-A}{2} +1 + ⌈\frac{-1}{2}⌉ = \frac{B-A}{2} +1 as ⌈\frac{-1}{2}⌉ = 0.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
assert(a >= 1 && b >= 1 && b <= 1e9 && a <= 1e9);
if (a == b) {
cout << "0\n";
} else if (b > a) {
cout << (b - a) / 2 + 1 << '\n';
} else {
if ((a - b) % 2 == 0) {
cout << (b - a) / 2 + 1 << '\n';
} else {
cout << (b - a) / 2 << '\n';
}
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int temp = floor((b - a) / 2.0);
if(a != b){
temp++;
}
cout<<temp<<"\n";
}
return 0;
}
[details=Editorialist’s Solution]
/*
* @author: vichitr
* @date: 24th July 2021
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
void solve() {
int A, B; cin >> A >> B;
int ans = 0;
if (A < B)
ans = (B - A) / 2 + 1;
else if (A > B) {
if ((A - B) % 2)
ans = (B - A) / 2;
else
ans = (B - A) / 2 + 1;
}
cout << ans << '\n';
}
signed main() {
fast;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}There is no need to check even or odd in code:
ll t;
cin >> t;
while (t--) {
ll a, b, res = 0;
cin >> a >> b;
if (a < b) {
res = 1 + (b - a) / 2;
} else {
res = (b - a + 1) / 2;
}
cout << res << "\n";
}
When a>b, f(B)={\lceil}\frac{B-A}{2}{\rceil},f(B+1)={\lceil}\frac{B-A+1}{2}{\rceil}, we known {\lceil}\frac{B-A+1}{2}{\rceil}\geqslant{\lceil}\frac{B-A}{2}{\rceil} when A > B. If B-A is odd they are equal.
1 Like
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
int a,b;
cin>>a>>b;
int ma=max(a,b);
int mi=min(a,b);
int r=-1e6;
for(int i=mi;i<=ma;i++){
int ans=ceil((b-i)/2)+ceil((i-a)/2);
r=max(ans,r);
}
cout<<r<<endl;
}
return 0;
}
why this code is giving wrong answer for some test cases?
Your code is giving TLE.
And maybe you should take r as -1e9 not -1e6.
Note: Don’t use inbuilt ceil function . Make your own function for calculating ceil.
Function for calculating ceil value of m/n i.e. ceil(m/n)
int find_ceil ( int m , int n ){
return ( m+n-1)/n;
}
buddy you are doing integer division change it to double
this doesn’t work. shows wrong answer