10901 - Ferry Loading III

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

Moderator: Board moderators

predator
New poster
Posts: 3
Joined: Sun Jun 25, 2006 6:33 pm
Location: Bangladesh
Contact:

Post by predator » Sun Jun 25, 2006 8:01 pm

i am having a difficulty in understanding the statement of the problem. can any one please explain me the 2nd sample

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Jul 23, 2006 9:36 pm

predator wrote:i am having a difficulty in understanding the statement of the problem. can any one please explain me the 2nd sample
At the begining the ferry is on the left bank waiting for a car. In 10 minutes a car arrives to the right bank while there is no car on the left bank at that time. Therefore, the ferry heads for the right bank. It arrives there at 20, loads the car and returns back to the left bank. After returning (at 30) it unloads the first car and loads the second one, as it has already come (at 25). Further it travels to the right bank, unloads the second car (at 40) and returns back on the left bank (at 50), again, where it loads the last car and deliver it to the right bank at 60.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Aug 26, 2006 7:57 pm

remember that the ith output is the exit time of the ith car, and the exit times are not necessarily sorted in nondecreasing time.

RED-C0DE
New poster
Posts: 16
Joined: Mon Mar 26, 2007 6:47 pm

Post by RED-C0DE » Fri Jul 20, 2007 5:44 pm

Please give me some Sample IO For this Problem... my program worked correctly with many IO samples...but WA... :(

tanks

ljacs
New poster
Posts: 5
Joined: Wed Sep 05, 2012 5:53 am

Why Wrong Answer?

Post by ljacs » Sun Oct 07, 2012 5:55 am

Please help.

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <stack>
#include <queue>
typedef unsigned long long ll;
using namespace std;

queue<int> l;
queue<int> r;

int main()
{
    int c; scanf("%d", &c);
    while (c--){
        int n,t,m;
        scanf("%d %d %d", &n, &t, &m);
        bitset<10000> posicoes;
        vector<int> listaL, listaR;
        posicoes.reset();
        int indice = 0;
        for (int i = 0; i<m; i++){
            int time; char side[10];
            scanf("%d %s", &time, side);
            if (side[0]=='l'){
                l.push(time);
            } else {
                r.push(time);
                posicoes[indice++] = true;
            }
        }
        
        int atual = 0;
        int carga;
        bool side = false;
        // false = left
        // true = right
        while (!l.empty() || !r.empty()){
            if (!l.empty() && !r.empty()) {
                if(l.front() > atual && r.front() > atual) {
                    if(l.front() > r.front()) {
                        atual += r.front() - atual;
                        if(!side) atual += t;
                        side = true;
                    }
                    else {
                        atual += l.front() - atual;
                        if(side) atual += t;
                        side = false;
                    }
                }
            } else {
                if (l.empty()) {
                    if (r.front() > atual) {
                        atual += r.front() - atual;
                        if(!side) atual += t;
                        side = true;
                    }
                }
                else {
                    if (l.front() > atual) {
                        atual += l.front() - atual;
                        if(side) atual += t;
                        side = false;
                    }
                }
            }
            if (!side) {
                carga = 0;
                while (carga < n && !l.empty() && l.front() <= atual) {
                    listaL.push_back(atual+t);
                    l.pop();
                    carga++;
                }
                atual += t;
                side = true;
            }
            else {
                carga = 0;
                while (carga < n && !r.empty() && r.front() <= atual) {
                    listaR.push_back(atual+t);
                    r.pop();
                    carga++;
                }
                atual += t;
                side = false;
            }
        }
        
        int indr=0, indl=0;
        for (int i = 0; i<m; i++){
            if (posicoes[i]){
                printf("%d", listaR[indr++]);
            } else printf("%d", listaL[indl++]);
            printf("\n");
        }
        if (c>0) printf("\n");
        listaL.clear();
        listaR.clear();
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10901 - Ferry Loading III

Post by brianfry713 » Sun Oct 07, 2012 10:44 pm

Input:

Code: Select all

1
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
Correct output:

Code: Select all

5
15
15
15
25
10
20
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Fri Dec 14, 2012 8:12 pm

brianfry713 wrote:Input:

Code: Select all

1
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
Correct output:

Code: Select all

5
15
15
15
25
10
20
@brianfry713... is it legal that arrival times are same ??? In arrival time 5 ,if a cargo comes in left bank,how at the same times another cargo can come in right bank ??? the problem statement says... " The arrival times for each test case are strictly increasing...." :(
I am really confused ... please help !!!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10901 - Ferry Loading III

Post by brianfry713 » Fri Dec 14, 2012 8:19 pm

Read this entire thread. Your question has already been answered by the problem setter.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Fri Dec 14, 2012 8:28 pm

brianfry713 wrote:Read this entire thread. Your question has already been answered by the problem setter.
Thanks a lot brianfry713.... for your quick reply... :)
It's my fault.... :x

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Fri Dec 14, 2012 8:41 pm

Got WA !!! Help please !!! :(

Code: Select all

Accepted......
Sorry for my bad coding... :(
Last edited by Mukit Chowdhury on Thu Dec 20, 2012 8:11 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10901 - Ferry Loading III

Post by brianfry713 » Fri Dec 14, 2012 9:06 pm

For input:

Code: Select all

1
1 5 2
0 left
0 left
My AC code prints:

Code: Select all

5
15
Instead of using a map, I just keep track of the finish times of the left and right queues, and the order of which side each input was.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Sat Dec 15, 2012 8:37 am

brianfry713 wrote:For input:

Code: Select all

1
1 5 2
0 left
0 left
My AC code prints:

Code: Select all

5
15
Instead of using a map, I just keep track of the finish times of the left and right queues, and the order of which side each input was.
I haven't understood what have you done... but I have used 4 queue this time... two are for value keeping and two are for index keeping of that values... would you give me some critical input for my code,please ???

Code: Select all

Accepted .........
Last edited by Mukit Chowdhury on Thu Dec 20, 2012 8:13 am, edited 3 times in total.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Sat Dec 15, 2012 8:46 am

for input...

Code: Select all

7
1 5 2
0 right
0 left
2 5 2
0 left
0 left
2 5 2
0 right
0 right
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
1 5 2
0 right
1 left
2 5 2
0 right
6 right
2 5 2
0 right
5 right
my codes shows...

Code: Select all

10
5

5
5

10
10

5
15
15
15
25
10
20

10
15

10
20

10
10
These are correct,right ???

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10901 - Ferry Loading III

Post by brianfry713 » Sat Dec 15, 2012 11:33 am

Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10901 - Ferry Loading III

Post by Mukit Chowdhury » Sat Dec 15, 2012 11:40 am

I tried there but haven't found any error ... :(
So I thought if you can find any bug seeing my code by your experience & can give me some critical input... :(
Would you,please?

Post Reply

Return to “Volume 109 (10900-10999)”