Page 1 of 1

10440 - Ferry Loading II

Posted: Wed Jul 21, 2004 4:47 am
by Zhou Yiyan@SHU
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?

Posted: Wed Jul 21, 2004 5:11 am
by Larry
Use a little greed. :)

Posted: Wed Jul 21, 2004 12:51 pm
by Zhou Yiyan@SHU
:oops: 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...

Posted: Tue Sep 28, 2004 4:56 pm
by jackie
Consider the last n cars they should be in one ferry for the optimization time.

10440 please help

Posted: Wed Aug 24, 2005 8:32 am
by vcchung
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!

Re: 10440 please help

Posted: Thu Aug 25, 2005 10:12 pm
by angga888
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 :D

Re: 10440 - Ferry Loading II

Posted: Tue Jan 13, 2009 8:07 am
by stcheung
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.

Re: 10440 - Ferry Loading II

Posted: Wed Oct 21, 2009 1:48 am
by buiutripa
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


thanks in advance! :)

Re: 10440 - Ferry Loading II

Posted: Wed Jun 16, 2010 12:45 am
by naseef_07cuet
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;
}
thanks in advance... :)

Re: 10440 - Ferry Loading II

Posted: Thu Dec 09, 2010 1:09 pm
by Shafaet_du
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

Re: 10440 - Ferry Loading II

Posted: Fri Jan 21, 2011 11:34 am
by zobayer
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
Thanks in advance :)

[EDIT]
The problem was, I didn't know that, printf evaluates it parameters right to left... like printf("%d %d\n", f(), b() ); printf first evaluates b and then f.