All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

10440 Ferry Loading II seems to be a search and optimization problem, but to my surprise, many solution only spent very little time. Is it a DP problem? I can't fnd the quick method, got TLE...and maybe WA that I don't ever know...
Could somebody give out some hint to solve the problem?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Use a little greed.

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China
I still couldn't believe it has such a simple solution... though I got AC. It seems that I have to look back to my student book about greedy algorithm...

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
Consider the last n cars they should be in one ferry for the optimization time.

vcchung
New poster
Posts: 1
Joined: Wed Aug 24, 2005 8:26 am

I am not very good at programming, but I am learning.

When I try to do 10440, but I found that it has many variations so that difficult to finish it.

Can anyone please give me some ideas, guidelines or algorithm for this problem??

Many thanks!

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

vcchung wrote:I am not very good at programming, but I am learning.

When I try to do 10440, but I found that it has many variations so that difficult to finish it.

Can anyone please give me some ideas, guidelines or algorithm for this problem??

Many thanks!
think about greedy algorithm

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10440 - Ferry Loading II

In case the hints aren't enough for the uninitiated. Basically you want to move the ferry when passenger #m (last passenger) has arrived, when passenger #(m-n) has arrived, when passenger #(m-2n) has arrived and so forth. But due to the roundtrip time, there will be some delay involved and so it boils down to calculating these delays.

buiutripa
New poster
Posts: 6
Joined: Wed Oct 21, 2009 1:44 am

### Re: 10440 - Ferry Loading II

anyone can help me to undertand this input/output:

in:

3
3 5 5
1 2 3 4
2 5 5
1 2 3 4
1 5 5
1 2 3 4

out:

17 2
7 1
9 1

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

### Re: 10440 - Ferry Loading II

I don't know what is the problem in my code. getting WA...can anyone help me...here is my code...

Code: Select all

``````#include<iostream>
using namespace std;
int main()
{
long cc,m,a[10000],i,j,k,l,mint,mintrip,c,n,t;
cin>>c;
for(i=0;i<c;i++)
{
cin>>n>>t>>m;
for(j=0;j<m;j++)
{
cin>>a[j];
}
mintrip=0;
int flag=0;
cc=0;
k=0;
for(j=0;j<m;j++)
{
if(flag!=1)
k=1;
cc=a[j];
if(j==0 && (m-n)>0)
{
j+=n-1;
cc=a[j-1];
mintrip++;
flag=0;
continue;
}
else if(m-(j+1)<=n && k<n && j!=0)
{
cc=a[m-1];
mintrip++;
break;
}
else if(a[j+1]-cc<=t && k<n)
{
flag=1;
k++;
continue;
}
flag=0;
mintrip++;
}
printf("%ld %ld\n",cc+t,mintrip);
}
return 0;
}
``````
If you have determination, you can do anything you want....

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

### Re: 10440 - Ferry Loading II

sample:

Code: Select all

``````2
2 5 5
6
7
10
12
14
2 5 6
6
7
10
12
14
33``````

Code: Select all

``````31 3
38 3
``````

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 10440 - Ferry Loading II

I am getting wrong answer. I have tried a greedy approach. All the existing tests passed, I also tried many cases. I need help to fix the bug. Here is what I have come up with.

Code: Select all

``````AC
``````