OJ Board

Posted: **Mon Mar 04, 2013 5:46 pm**

mahade hasan wrote:getting TLE....
Help need ...

You may try these cases:

Input

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

Posted: **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

My output

Code: Select all

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;
}

Posted: **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;
}

Posted: **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.

Posted: **Mon Sep 30, 2013 2:58 am**

Why WA ?
http://ideone.com/AQnsSi

Posted: **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

Posted: **Tue Oct 01, 2013 4:31 am**

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

Posted: **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.

Posted: **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!!!!

Posted: **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

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?

OJ Board

10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III

Re: 10901 - Ferry Loading III