COCR104 - EDITORIAL

Author: Sumeet Pachauri
Tester: Darshan Lokhande
Editorialist: Vaibhav Chauhan

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++;

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;
}

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

5 Likes

https://www.codechef.com/viewsolution/34527860

1 Like

there are some problem with this code i request u to refer any of the above code in editorial ur code have a starting point problem as markings will start from 0 itself and we are not sure that where L lies with respect to last flag

1 Like

Can you please share a test case where it fails

ya sure
10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000

1 Like

try with this test case here T==10 only and in our question we have T = 10^5

Thank you

1 Like