In this HackerEarth Raj & his Slippers problem solution, Raj stays at a hostel. He has N friends, numbered from 1 to N.
One day, when he woke up at time p:q, he found his slippers to be missing.
He couldn't go out to get a new slipper on bare foot. So, he wants to borrow slippers from one of his friends to go to the store to get a new slipper. But there are 5 conditions he must follow:
The hostel has an in-time of x:y . He has to return back before x:y.
The footwear store in that area opens at a time a:b, only after which a slipper can be selected and bought, no matter how early Raj goes to the shop. Once the shop is opened, it stays open throughout the day.
He can borrow the slippers from his friend numbered x, only if x does not use his slippers in the time interval that Raj asks for.
Luckily, all of Raj's friends are lazy and hence they use their slippers exactly once a day. For each friend, you are given h1:m1 and h2:m2. The friend uses his slippers from h1:m1 to h2:m2 (inclusive)
if Raj has the option to use the slippers of friend i and friend j such that i<j, he would prefer to use the slipper of friend i.
It takes Raj R minutes to travel from the store to his hostel and from his hostel to the store, both . Once he is at the store, it takes him S minutes to select a new slipper.
Raj wants to go to the footwear store, select and buy a new slipper and return to the hostel at the earliest. Given all the required information, find the friend from whom Raj should borrow the slippers.
He can start his journey after he wakes up, that is, after p:q
HackerEarth Raj & his Slippers problem solution.
#include <stdlib.h>
#include <time.h>
#include<stdio.h>
int max(int a,int b)
{
return (a>b)?a:b;
}
int wakes_after_intime(int a, int b)
{
if(a>=b)
return 1;
return 0;
}
int cant_go_to_store(int a, int b)
{
if(a>=b)
return 1;
return 0;
}
main()
{
int t;
scanf("%d",&t);
int t1=t;
while(t--)
{
printf("Case %d: ",t1-t);
int n,select_time,walking_time,i,j,wake_mins=0,wake_hours=0;
scanf("%d",&n);
char in_time[10], wake_time[10],store_opening_time[10];
scanf("%s%s%s",in_time,wake_time,store_opening_time);
scanf("%d%d",&walking_time,&select_time);
if(n==0)
{
printf("-1\n");
continue;
}
//printf("intime = %s\nwake time = %s\nstore opens ate %s\nwalking time= %d\nselect time = %d\n",in_time,wake_time,store_opening_time,walking_time,select_time);
char friends[1+n][2][10];
for(i=0;i<n;i++)
{
scanf("%s%s",friends[i][0],friends[i][1]);
//printf("The stats of %dth friend = %s to %s\n ",i,friends[i][0],friends[i][1]);
}
int in_time_mins=0,in_time_hours=0;
if(in_time[1]==':') // hours<10
{
in_time_hours=(int)in_time[0]-48;
for(j=2;in_time[j]!='\0';j++)
{
in_time_mins=in_time_mins*10+ (int)in_time[j]-48;
}
}
else
{
in_time_hours=((int)in_time[0]-48)*10 + (int)in_time[1]-48;
for(j=3;in_time[j]!='\0';j++)
{
in_time_mins=in_time_mins*10+ (int)in_time[j]-48;
}
}
in_time_mins+= in_time_hours*60;
//printf("intime = %d\n",in_time_mins);
if(wake_time[1]==':') // hours<10
{
wake_hours=(int)wake_time[0]-48;
for(j=2;wake_time[j]!='\0';j++)
{
wake_mins=wake_mins*10+ (int)wake_time[j]-48;
}
}
else
{
wake_hours=((int)wake_time[0]-48)*10 + (int)wake_time[1]-48;
for(j=3;wake_time[j]!='\0';j++)
{
wake_mins=wake_mins*10+ (int)wake_time[j]-48;
}
}
wake_mins+= wake_hours*60;
int store_opening_hours=0,store_opening_mins=0;
if(store_opening_time[1]==':') // hours<10
{
store_opening_hours=(int)store_opening_time[0]-48;
for(j=2;store_opening_time[j]!='\0';j++)
{
store_opening_mins=store_opening_mins*10+ (int)store_opening_time[j]-48;
}
}
else
{
store_opening_hours=((int)store_opening_time[0]-48)*10 + (int)store_opening_time[1]-48;
for(j=3;store_opening_time[j]!='\0';j++)
{
store_opening_mins=store_opening_mins*10+ (int)store_opening_time[j]-48;
}
}
store_opening_mins+= store_opening_hours*60;
if(wakes_after_intime(wake_mins, in_time_mins))
{
//Raj wokes up after intime.... So, he can't go to store today.
printf("-1\n");
continue;
}
if(cant_go_to_store(store_opening_mins,in_time_mins))
{
//cant go to store because, the store opens only after hostel's intime
printf("-1\n");
continue;
}
int can_borrow[3600]={1},reqd_time= 2*walking_time+select_time,mini=5000,current_best=-1;
if(reqd_time>in_time_mins)
{
printf("-1\n");
continue;
}
int start=max(wake_mins,store_opening_mins-walking_time);
//printf("See here...intime= %d\nwake_mins= %d\nstoreopen = %d\n",in_time_mins,wake_mins,store_opening_mins);
//printf("Reqd duration of the borrowed slipper =%d\nMin_Start time of the slipper hunt = %d\n",reqd_time,start);
if(start+reqd_time >=in_time_mins)
{
printf("-1\n");
continue;
}
int yes=0;
for(i=0;i<n;i++)
{
int st_hours=0, st_mins=0,end_hours=0,end_mins=0;
if(friends[i][0][1]==':') // hours<10
{
st_hours=(int)friends[i][0][0]-48;
for(j=2;friends[i][0][j]!='\0';j++)
{
st_mins=st_mins*10+ (int)friends[i][0][j]-48;
}
}
else
{
st_hours=((int)friends[i][0][0]-48)*10 + (int)friends[i][0][1]-48;
for(j=3;friends[i][0][j]!='\0';j++)
{
st_mins=st_mins*10+ (int)friends[i][0][j]-48;
}
}
if(friends[i][1][1]==':') // hours<10
{
end_hours=(int)friends[i][1][0]-48;
for(j=2;friends[i][1][j]!='\0';j++)
{
end_mins=end_mins*10+ (int)friends[i][1][j]-48;
}
}
else
{
end_hours=((int)friends[i][1][0]-48)*10 + (int)friends[i][1][1]-48;
for(j=3;friends[i][1][j]!='\0';j++)
{
end_mins=end_mins*10+ (int)friends[i][1][j]-48;
}
}
st_mins+=st_hours*60;
end_mins+=end_hours*60;
//printf("friend %d : \t%d,%d\n",i+1,st_mins, end_mins);
if(end_mins<start || start+reqd_time< st_mins)
{
printf("%d\n",i+1);
yes=1;
break;
}
else
{
if(end_mins+1+reqd_time<in_time_mins && end_mins+reqd_time < mini)
{
mini=end_mins+reqd_time;
current_best=i;
// printf("\nCurrent best has been changed to %d\n",current_best);
}
}
}
if(yes)
{
continue;
}
if(current_best==-1)
{
printf("-1\n");
continue;
}
else
printf("%d\n",current_best+1);
}
return 0;
}Second solution
#include <bits/stdc++.h>
using namespace std;
#define MAX(x,y) ((x)>(y)?(x):(y))
int main()
{
int t,T;
scanf(" %d",&T);
assert(T>=1 && T<=100);
for(t=1;t<=T;t++)
{
int i,n;
int back1,back2;
scanf(" %d",&n);
assert(n>=0 && n<=200);
int inh,inm,wakeh,wakem,openh,openm;
scanf(" %d:%d %d:%d %d:%d",&inh,&inm,&wakeh,&wakem,&openh,&openm);
assert(inh>=0 && wakeh>=0 && openh>=0 && inh<24 && wakeh<24 && openh<24);
assert(inm>=0 && wakem>=0 && openm>=0 && inm<60 && wakem<60 && openm<60);
int traveltime,selecttime;
scanf(" %d %d",&traveltime,&selecttime);
assert(traveltime>=0 && selecttime>=0 && traveltime<24*60 && selecttime<24*60);
int in=inh*60+inm,wake=wakeh*60+wakem,open=openh*60+openm;
int done=-1;
int earliest=-1;
for(i=0;i<n;i++)
{
int start,end,a,b;
scanf(" %d:%d",&a,&b);
assert(a>=0 && b>=0 && a<24 && b<60);
start=a*60+b;
scanf(" %d:%d",&a,&b);
end=a*60+b;
assert(a>=0 && b>=0 && a<24 && b<60);
assert(end>=start);
back1=(MAX(open,wake+traveltime)+selecttime+traveltime);
if(back1<start && back1<in)
{
if(earliest==-1 || earliest>back1)
{
earliest=back1;
done=i+1;
}
}
back2=MAX(open,(MAX(end,wake)+traveltime))+selecttime+traveltime;
if(back2<in)
{
if(earliest==-1 || earliest>back2)
{
earliest=back2;
done=i+1;
}
}
}
printf("Case %d: %d\n",t,done);
}
return 0;
}
0 Comments