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:

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

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

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:

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:

``````AC