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

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10901 - Ferry Loading III

Post by lbv » Mon Mar 04, 2013 5:46 pm

mahade hasan wrote:getting TLE....
Help need ...
You may try these cases:

Input

Code: Select all

2
2 24 7
2 right
7 left
12 right
22 right
34 right
73 right
76 right
4 3 8
5102 left
8090 right
9875 left
14954 left
19584 right
31434 left
76546 left
77138 left
Output

Code: Select all

50
74
50
98
98
146
146

5105
8093
9878
14960
19587
31437
76552
77144

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 10901 - Ferry Loading III

Post by Munchor » Sat Apr 06, 2013 8:57 pm

Code: Select all

2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left
2 10 3
10 right
25 left
40 left
3 5 7
0 left
1 left
2 left
3 left
5 left
5 right
11 right
2 24 7
2 right
7 left
12 right
22 right
34 right
73 right
76 right
I get all those cases correct. However, I get these two wrong:

Code: Select all

1 10 3
0 left
10 right
30 left
4 3 8
5102 left
8090 right
9875 left
14954 left
19584 right
31434 left
76546 left
77138 left
Correct output

Code: Select all

10
20
40

5105
8093
9878
14960
19587
31437
76552
77144
My output

Code: Select all

10
20
50

8099
8096
9881
14960
31443
31440
76552
77144
So I'm not that far away, I'm doing something wrong and I can't find out what, here's my full code:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

struct boat
{
  int arrival_time;
  int final_time;
  int index;
};

int cases, n, t, m, i, v, time, new_boat_time, boats_carrying;
bool left_side;
char side[6];
queue<boat> right, left;
vector<boat> output;

void read_input()
{
  scanf("%d %d %d", &n, &t, &m);

  output.clear();
  
  for (i = 0; i < m; i++)
  {
    scanf("%d %s", &new_boat_time, side);

    boat new_boat;
    new_boat.arrival_time = new_boat_time;
    new_boat.final_time = 0;
    new_boat.index = (int) output.size();

    if (strcmp(side, "right") == 0)
    {
      right.push(new_boat);
    }
    else
    {
      left.push(new_boat);
    }
    
    output.push_back(new_boat);
  }
}

int main()
{
  scanf("%d", &cases);

  for (v = 0; v < cases; v++)
  {
    read_input();
    left_side = true;
    time = 0;

    while (!(right.empty() && left.empty()))
    {
      boats_carrying = 0;

      if (left_side)
      {
        for (i = 0; i < n; i++)
        {
          if (!left.empty())
          {
            if (left.front().arrival_time <= time)
            {
              //printf("%d\n", time + t);
              output[left.front().index].final_time = time + t;
              left.pop();
              boats_carrying++;
            }
          }
        }

        if (boats_carrying > 0)
        {
          time += t;
        }
        else
        {
          if (right.front().arrival_time > time)
          {
            time += t + right.front().arrival_time - time;
          }
          else
          {
            time += t;
          }
        }
      }
      else
      {
        for (i = 0; i < n; i++)
        {
          if (!right.empty())
          {
            if (right.front().arrival_time <= time)
            {
              //printf("%d\n", time + t);
              output[right.front().index].final_time = time + t;
              right.pop();
              boats_carrying++;
            }
          }
        }

        if (boats_carrying > 0)
        {
          time += t;
        }
        else
        {
          if (left.front().arrival_time > time)
          {
            time += t + left.front().arrival_time - time;
          }
          else
          {
            time += t;
          }
        }
      }

      left_side = !left_side;
    }

    for (i = 0; i < (int) output.size(); i++)
    {
      printf("%d\n", output[i].final_time);
    }
    
    if (v != cases - 1)
    {
      printf("\n");
    }
  }

  return 0;
}

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 10901 - Ferry Loading III

Post by a.elbashandy » Sun Apr 07, 2013 12:16 am

I passed all the test cases and it still got WA, can anyone please help me ?

Code: Select all

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    int T; scanf("%d", &T);
    while(T--){
        queue< pair<int, int> > leftQ, rightQ;
        int n, t, m;
        scanf("%d %d %d", &n, &t, &m);
        
        char buff[10];
        int z;
        string s;
        vector<int> v;
        for (int i = 0; i < m; i++) {
            scanf("%d %s", &z, buff);
            s = buff;
            if(s == "left")
                leftQ.push(make_pair(z, i));
            else
                rightQ.push(make_pair(z, i));
            v.push_back(0);
        }
        
        int totalTime = 0;
        bool left = true;
        bool first = true;
        while(!leftQ.empty() || !rightQ.empty()){           
            
            if(left && !leftQ.empty()){
                int k = 0;
                totalTime += t;
                for (int i = 0; i < n; i++) {
                    int a = leftQ.front().first;
                    if((totalTime-t) >= a && !leftQ.empty()) k++;
                    else break;
                    v[leftQ.front().second] = totalTime;
                    //printf("%d\n", totalTime);
                    leftQ.pop();
                }
                
                if(!k){
                    if(!rightQ.empty() && rightQ.front().first < leftQ.front().first) totalTime += abs((totalTime-t) - rightQ.front().first);
                    else{
                        int a = leftQ.front().first;
                        int x = a;
                        if((totalTime-t) < a) 
                            totalTime += a - (totalTime-t);
                        v[leftQ.front().second] = totalTime;
                        //printf("%d\n", totalTime);
                        leftQ.pop();
                        for (int i = 1; i < n && !leftQ.empty(); i++) {
                            a = leftQ.front().first;
                            if(a > x) break;
                            v[leftQ.front().second] = totalTime;
                            //printf("%d\n", totalTime);
                            leftQ.pop();
                            if(leftQ.empty()) break;
                        }
                    }
                }                                
                left = false;
            }else if(!left && !rightQ.empty()){
                int k = 0;
                totalTime += t;
                for (int i = 0; i < n; i++) {
                    int a = rightQ.front().first;
                    if((totalTime-t) >= a && !rightQ.empty()) k++;
                    else break;
                    v[rightQ.front().second] = totalTime;
                    //printf("%d\n", totalTime);
                    rightQ.pop();
                }
                
                if(!k){
                    if(!leftQ.empty() && leftQ.front().first < rightQ.front().first) totalTime += abs((totalTime - t) - leftQ.front().first);
                    else{
                        int a = rightQ.front().first;
                        int x = a;
                        if((totalTime-t) < a) totalTime += a - (totalTime-t);
                        v[rightQ.front().second] = totalTime;
                        //printf("%d\n", totalTime);
                        rightQ.pop();
                        for (int i = 1; i < n && !rightQ.empty(); i++) {
                            a = rightQ.front().first;
                            if(a > x) break;
                            v[rightQ.front().second] = totalTime;
                            //printf("%d\n", totalTime);
                            rightQ.pop();
                            if(rightQ.empty()) break;
                        }
                    }
                        
                }
                left = true;
            }else{
//                totalTime += t;
//                left = (left) ? false: true;
                if(left && !rightQ.empty()){
                    if(totalTime < rightQ.front().first){
                        totalTime += abs(totalTime - rightQ.front().first) + t;
                    }else{
                        totalTime += t;
                    }
                    left = false;
                }else if(!left && !leftQ.empty()){
                    if(totalTime < leftQ.front().first){
                        totalTime += abs(totalTime - leftQ.front().first) + t;
                    }else{
                        totalTime += t;
                    }
                    left = true;
                }
            }
        }
        
        for (int i = 0; i < v.size(); i++) {
            printf("%d\n", v[i]);
        }

        
        if(T) printf("\n");
    }
    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 » Tue Apr 09, 2013 11:46 pm

Munchor, for input:

Code: Select all

1 10 3
0 left
10 right
30 left
Correct output

Code: Select all

10
20
40
Your output

Code: Select all

10
20
50
At time 20 the ferry is at the left bank and no cars are waiting so it shouldn't move. At time 30 when the car arrives at the left bank it should be transported to the right bank. I'm guessing your code has the empty ferry moving to the right bank at time 20.

a.elbashandy, it looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10901 - Ferry Loading III

Post by cyberdragon » Mon Sep 30, 2013 2:58 am


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 » Tue Oct 01, 2013 1:23 am

Input:

Code: Select all

1
1 5 2
0 left
0 left
AC output:

Code: Select all

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

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

Re: 10901 - Ferry Loading III

Post by cyberdragon » Tue Oct 01, 2013 4:31 am

"The arrival times for each test case are strictly increasing."
This case is invalid.

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 » Tue Oct 01, 2013 11:36 pm

There is a case in the judge's input where two consecutive arrival times are equal. The problem statement should actually say non-decreasing instead of strictly increasing.
Check input and AC output for thousands of problems on uDebug!

doried_a_a
New poster
Posts: 1
Joined: Sat Oct 12, 2013 3:22 pm

Re: 10901 - Ferry Loading III

Post by doried_a_a » Sat Oct 12, 2013 1:22 pm

Hello every body,
this problem made me go crazy!
here is my code, which passed all the test given by this thread as (correct tests).

Code: Select all

AC! without changing my code!!! 
I've noticed that UVa toolkit dosen't produce correct output!
Please, Help!!!!

sith
Learning poster
Posts: 70
Joined: Sat May 19, 2012 7:46 pm

Re: 10901 - Ferry Loading III

Post by sith » Mon Sep 04, 2017 5:44 pm

Hi

could somebody explain why this input

Code: Select all

1
2 2 1
3 right
produces result

Code: Select all

7
If ferry starts from the left bench, it should stay there as there are no cars on either of banks until 3. after it it will take 1 to get to the right bank and 1 to travel back. So it should be 5.

Why is it 7?

Post Reply

Return to “Volume 109 (10900-10999)”

Who is online

Users browsing this forum: No registered users and 1 guest