/*
There is one boat and a boatman to take travelers from either side of the river bank to the other side. The boat takes n people in a single trip and takes t minutes to reach the other side. Neglect the influence of river currents and direction of the flow and assume that the boat takes the same time to cross the river in either direction. m people want to cross the river in the entire day and come at different times during the day. The method getTripTime holds 4 parameters such as people is the n, minutes is the t, noofpeoples is the m and integer pointer array variable arrival gives the arrival time of each people.
What is the earliest time that all the people can travel across the river by the boat?
What is the minimum number of trips that the boat must make to cross all people by that time?
0 > n, m, t <=1000
Write a C/C++ program to find the earliest time and minimum number of trips.
Example:
Input
people = 5;
minutes = 10;
noofpeople = 11;
arrival[] = {4,7,9,17,17,18,27,27,31,32,35}
Here people is the number of persons the boat can accommodate. minutes is the time taken to travel from one end to another. noofpeople is the total number of travelers waiting to cross the river. arrival[] is the arrival time of the travelers.
Output
Returns 54 Minutes and 3 Trips. 54 is the earliest time and 3 is the number of trips.
*/
#include<stdio.h>
int* getTripTime(int people, int minutes, int noofpeoples, int* arrival);
void main()
{
int people = 5, minutes = 10, noofpeoples = 14,
arrival[] ={4,7,9,17,17,18,27,27,31,32,35,40,60,65};
int *ans;
clrscr();
ans = getTripTime(people, minutes, noofpeoples, arrival);
printf("\n%d Minutes and %d Trips. ",ans[0], ans[1]);
printf(" %d is the earliest time and %d is the number of trips. ",ans[0], ans[1]);
getch();
}
int* getTripTime(int people, int minutes, int noofpeoples, int* arrival)
{
int *diff, min_minutes = 0, nooftrip = 0;
int i, firsttrip, pcount=0, mcount = 0, *ans;
ans = (int *)malloc(sizeof(int) * 2);
diff = (int *)malloc(sizeof(int) * noofpeoples);
diff[0] = 0;
for(i=1;i<noofpeoples;i++)
{
diff[i ] = arrival[i ] - arrival[i-1];
}
// for(i=0;i<noofpeoples; i++)
// printf("\n%d",diff[i ]);
firsttrip = noofpeoples % people;
for(i=0; i<firsttrip; i++)
{
min_minutes += arrival[i ];
}
if(firsttrip) nooftrip++;
for(i=firsttrip; i<noofpeoples; nooftrip++)
{
pcount = 0, mcount = 0;
while(pcount<people && mcount < 2*minutes)
{
mcount += diff[i ];
pcount++; i++;
}
if(mcount > 2*minutes)
{
i--;
mcount -= diff[i ];
}
}
min_minutes += nooftrip*2*minutes - minutes;
ans[0] = min_minutes;
ans[1] = nooftrip;
printf("\n%d Minutes and %d Trips. ",min_minutes, nooftrip);
printf(" %d is the earliest time and %d is the number of trips. ", min_minutes, nooftrip);
return(ans);
}
