PROBLEM LINK: Marking the Borders
Author: Sumeet Pachauri
Tester: Darshan Lokhande
Editorialist: Vaibhav Chauhan
Difficulty:
Cakewalk
Prerequisites:
Arithmatic Progression, Basic Math
Problem:
Given an infinite positive x axis , where markings are placed at (a) , (a+b) , (a+b+a) , (a+b+a+b) , ..... units. Find the number of markings placed between L and R units (inclusive of L and R).
Explanation:
Key observation is that 1st , 3rd , 5th… markings form an Arithmatic progression (with common difference (a+b)). Similarly the 2nd , 4th , 6th… markings too form an Arithmatic Progression with the same common difference (a+b). Simple way to find the required answer is to find the total number of markings in [0,R] and subtract the number of markings present in [0,L-1]. In general the number of markings in [0,X] can be found out by adding the number of terms in both the AP’s.
ll terms = 0; ll diff = a + b; if (X >= a) terms += (X - a) / (diff) + 1; //Terms of First AP if (X >= a + b) terms += (X - a - b) / (diff) + 1; //Terms of second AP
Solution:
Setter's Solution
#include<bits/stdc++.h>
#define ull unsigned long long int
#define r0 return 0
#define test int T;cin>>T;while(T--)
#define pb push_back
#define int long long
#define vi vector<int>
#define si set<int>
#define msi multiset<int>
#define mii map<int, int>
#define pi pair<int, int>
#define F first
#define S second
#define MOD 1000000007
#define MAXN 100001
using namespace std;
signed main()
{ test{
int x, y, l, r;
cin>>x>>y>>l>>r;
//counting till r
int ctr;
ctr=2*(r/(x+y));
if(r%(x+y)>=x)ctr++;
//counting till l while skipping the count if l%(x+y)=0
int ctl;
ctl=2*(l/(x+y));
if(l%(x+y)>x)ctl++;
//calculating the answer
int ans=ctr-ctl;
//checking if a term of the progression with x+y as common difference coincides with l
if(l%(x+y)==0&&l!=0)ans++;
cout<<ans<<"\n";
}
r0;
}
Tester's Solution
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll long long int
#define ld long double
#define mk make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define MOD 1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;
ll a, b;
ll work(ll num) {
ll tot = 0;
ll diff = a + b;
if (num >= a) tot += (num - a) / (diff) + 1;
if (num >= a + b) tot += (num - a - b) / (diff) + 1;
return tot;
}
int main()
{
boost;
ll t;
cin >> t;
while (t--)
{
ll l, r;
cin >> a >> b >> l >> r;
cout << work(r) - work(l - 1) << '\n';
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define ull unsigned long long int
#define r0 return 0
#define test int T;cin>>T;while(T--)
#define pb push_back
#define ll long long
#define vi vector<int>
#define si set<int>
#define msi multiset<int>
#define mii map<int, int>
#define pi pair<int, int>
#define F first
#define S second
#define MOD 1000000007
#define MAXN 100001
using namespace std;
ll count(ll a, ll b, ll limit)
{
ll initialcount=limit/(a+b);
ll ans=2*initialcount;
if(limit%(a+b)>= a)
ans++;
return ans;
}
int main()
{
test{
ll a, b, l, r;
cin >> a >> b >> l >> r;
ll ctr=count(a, b, r);
ll ctl=count(a, b, l);
if((l % (a+b)==a || l % (a+b)==0)&&l!=0)
cout <<ctr-ctl+1<< "\n";
else if(l==0)
cout<<ctr<<"\n";
else
cout <<ctr-ctl<< "\n";
}
r0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 