10440 - Ferry Loading II

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

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

10440 - Ferry Loading II

Post 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?

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

Post by Larry »

Use a little greed. :)

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

Post 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...

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie »

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

10440 please help

Post 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!

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

Re: 10440 please help

Post 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

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

Re: 10440 - Ferry Loading II

Post 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.

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

Re: 10440 - Ferry Loading II

Post 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! :)

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 10440 - Ferry Loading II

Post 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... :)
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

Post 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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10440 - Ferry Loading II

Post 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.
You should not always say what you know, but you should always know what you say.

Post Reply

Return to “Volume 104 (10400-10499)”