PROBLEM LINK:
Setter: Chiraag Mittal
Tester: Jatin Nagpal
Editorialist: Chiraag Mittal
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
For Each Test Case , we have been given N the number of boxes. The next line contains N numbers i.e. the number of candies in each box.
Third line contains an integer X i.e. the speed .
A eats candies in leftmost box with a speed X times faster than B. We need to find the number of boxes finished by A and B.
EXPLANATION:
We need to find for A as well as for B, the time they will start eating candies in each of the N boxes. If the time A will start eating candies in a box<=time B will start eating candies in that box ,then increase the count for A else increase the count for B.
A start eating candies from the left (index 0) with a speed X times faster than of B and B starts eating candies from the right (index n-1) .For each box, we need to find who will reach to that box faster as candies from a particular box can only be eaten by either of A and B. Whosoever reaches to a box faster will eat all the candies in that box.
Let at a given time,A has eaten P candies and B has eaten Q candies. 3 possible cases are as follows:
Case 1 : P < X * Q
In this case , A will eat all the candies from the next box form left.
Case 2 : P > X * Q
In this case , B will eat all the candies from the next box from right .
Case 3 : P = X * Q
In this case , as both A and B have reached to same box but candies in a box can eaten be only one of them, so we need to check who has eaten more number of boxes till now.
SOLUTION:
Setter
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,x;
cin>>n;
int i=0,j=n-1;
int arr[n+1];
for(int i=0;i<n;i++)
cin>>arr[i];
cin>>x;
int count1=0,count2=0;
ll sum1=0,sum2=0;
while(i<j)
{
if(sum1>sum2)
{
sum2+=(x*arr[j]);
count2++;
j--;
}
else if(sum2>sum1)
{
sum1+=arr[i];
i++;
count1++;
}
else
{
sum2+=(x*arr[j]);
count2++;
j--;
sum1+=arr[i];
i++;
count1++;
}
}
if(i==j && sum1<sum2)
count1++;
else if(i==j && sum1>sum2)
count2++;
else
{
if(count1>=count2) count1++;
else count2++;
}
cout<<count1<<" "<<count2<<"\n";
}
return 0;
}
Tester
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f1(i,a,b) for(i=a;i<b;i++)
#define f2(i,a,b) for(i=a;i>=b;i--)
int i,j;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
f1(i,0,n)
{
cin>>a[i];
}
int x;
cin>>x;
int left=0,right=n-1;
int candy1=0,candy2=0;
int box1=0,box2=0;
while(left<=right)
{
if(candy1<x*candy2)
{
candy1+=a[left];
box1++;
left++;
}
else if(candy1>x*candy2)
{
candy2+=a[right];
box2++;
right--;
}
else
{
if(left!=right)
{
candy1+=a[left];
left++;
box1++;
}
else
{
if(box1<box2)
{
candy2+=a[right];
box2++;
right--;
}
else
{
candy1+=a[left];
left++;
box1++;
}
}
}
}
cout<<box1<<" "<<box2<<endl;
}
return 0;
}
Feel free to share your approach, if you want to . Suggestions are welcomed as always had been. 