I have sorted the array in the decreasing number of months required by each tree. FUNCTION (MergeSort())
Then checking Linearly for required wood in “for loop” of main.
plz somebody answer
Can you explain your approach? It’s hard to figure out what is happening.
1 Like
eg.
3 74 51
2 2
5 7
2 9
i am sorting both the array based on the number of months needed
let for 2 2
(51-2)/2 =24.5 months will need to grow upto 51
similarly (51-5)/7=6.57 moths,(51-2)/9=5.44
hence array after sorting will be
2 2
5 7
2 9
now i will ckeck from last
if a single tree’s wood is greater than required tree i will break else i will add the other trees wood
@jeetu86044 in certain cases your answer is becoming a negative value such as the input here. A simple check can fix the problem, I have marked it as “BUG FIX”, and making the change gives AC.
I also found another bug where the output comes as 1 instead of 0. Using the library function ceill instead of your own ciel seems to fix this.
There may be other bugs, I didn’t look further, but I hope this satisfies you. By the way, it’s an nice approach for the problem 
1 Like
CodeChef is a non-commercial competitive programming community Hello vamsi_223
Logout
PRACTICE
COMPETE
DISCUSS
COMMUNITY
HELP
ABOUT
CodeChef SnackDown 2017Compete & win $20.5K Qualifier starts on 20 May, SAT 5:00 PM IST Duration: 96 hrs
31
Days
5
Hrs
22
Min
16
Sec Register Now
Home » Forest Gathering » All Submissions » jeetu86044 [13370771]
Solution: 13370771
CodeChef submission 13370771 (C++ 4.9.2) plaintext list. Status: AC, problem FORESTGA, contest CODECHEF. By jeetu86044 (jeetu86044), 2017-04-22 00:37:37.
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define ll long long int
void MergeSort(ll *p,ll *q,ll low,ll high,ll min);
void Merge(ll p,ll q,ll low,ll mid,ll high,ll min);
ll ciel(long double n);
int main(){
ll n,in[1000000],rt[1000000],req,min,re=9223372036854775807,count=0,sum1=0,sum=0,count1,diff,sum3=0,flag=0,i;
long double x=1.0000000000000000000;
scanf("%lld%lld%lld",&n,&req,&min);
for(i=0;i<n;i++){
scanf("%lld%lld",&in[i],&rt[i]);
}
MergeSort(in,rt,0,n-1,min);
for(i=n-1;i>=0;i–){
count1=ciel((long double)(min-in[i])/(rt[i]x));
// printf("%lld re\n",re);
diff=count1-count;
if(count1>=re){
printf("%lld\n",re);
flag=1;
break;
}
sum=(count1rt[i]+in[i])+sum1diff+sum;
sum1=sum1+rt[i];
sum3=sum3+in[i];
if(sum>=req){
printf("%lld\n",count1);
flag=1;
break;
}
else{
re=ciel((long double)(req-sum3)/(sum1x));
count=count1;
}
}
if(!flag)
printf("%lld\n",re);
return 0;
}
ll ciel(long double n){
ll n1;
long double x=0.00000000000000000000;
n1=n;
n=n-n1;
if(n==x)
return n1;
else return (n1+1);
}
void MergeSort(ll *p,ll *q,ll low,ll high,ll min){
ll mid;
if(low<high){
mid=(low+high)/2;
MergeSort(p,q,low,mid,min);
MergeSort(p,q,mid+1,high, min);
Merge(p,q,low,mid,high,min);
}
}
void Merge(ll p,ll q,ll low,ll mid,ll high,ll min){
ll k,i,j,b[1000000],c[1000000];
long double x,y,z=1.000000000000000;
i=low,j=mid+1,k=0;
while(i<=mid&&j<=high){
x=((p+i)-min)/( (q+i)z);
y=((p+j)-min)/( (q+j)z);
if(x<y){
b[k]=(p+i);
c[k]=(q+i);
i++,k++; }
else{
b[k]=(p+j);
c[k]=(q+j);
j++,k++;
}
}
while(i<=mid){
b[k]=(p+i);
c[k]=(q+i);
i++,k++;
}
while(j<=high){
b[k]=(p+j);
c[k]=(q+j);
j++,k++;
}
for(i=low,j=0;i<=high;i++,j++){
*(p+i)=b[j];
*(q+i)=c[j];
}
}
No problem