11034 - Ferry Loading IV

[sunnycare]

simple problem , but i got WA...
need some test cases...(i also want to know how to generate them )
my code is here?if you have time please check it...

Code: Select all

#include <iostream>
#include <cstdlib>
using namespace std;
//11034
int main()
{
	int cases;
	cin>>cases;
	int l,m,cl,cnt,s;
	char curSide;
	char side[16];
	while(cases-->0)
	{
		cin>>l;
		l*=100;
		cin>>m;
		cnt=0;
		curSide='l';
		s=0;
		
		while(m-->0)
		{
			cin>>cl>>side;
			if(side[0]!=curSide)
			{
				cnt++;
				curSide=side[0];
				s=cl;
			}
			else
			{
				if(s+cl>l)
				{
					cnt+=2;
					s=cl;
				}
				else
				{
					s+=cl;
				}
			}
		}
		if(s!=0)
			cnt++;
		cout<<cnt<<endl;
	}
}

[dumb dan]

The ferry is initially on the left bank where it broke and it took quite some time to fix it. In the meantime, lines of cars formed on both banks that await to cross the river.

In other words, cars on left side never have to wait on cars on the right side and vice verca. Two seperate waiting lines.

Input:

Code: Select all

1
10 2
300 right
300 left

Output:

Code: Select all

2

[sunnycare]

thanks...i know...

[dik]

Why I got TL ???

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {

	long n,m,l;
	vector< pair<long,string> > cars;

	cin >>n;
	while (n--) {
		cin >>l >>m;
		l*= 100;

		cars.clear();

		while (m--) {
			long len;
			string bank;

			cin >>len >>bank;

			cars.push_back(make_pair(len, bank));
		}

		string bank= "left";
		long ans= 0;
		while (!cars.empty()) {
			long suml= 0;
			for (int i= 0; i!=cars.size() && suml<l; ) {
				if (cars[i].second== bank && suml+cars[i].first<=l) {
					suml+= cars[i].first;
					cars.erase(cars.begin()+i);
				}
				else i++;
			}
			if (bank=="left") bank= "right";
			else bank= "left";

			ans++;
		}

		cout <<ans <<endl;
	}

	return 0;
}

[Martin Macko]

Why I got TL ???

Note that cars.erase(cars.begin()+i) takes O(cars.size()) time. Therefore, the time complexity of your algorithm is O(m^2) and there is no chance to get it accepted. Try to use list<T> instead of vector<T>.

[yeasin_acm_solver]

plz anybody help me, i can't understand why my code getting wrong answer.

Code: Select all

/*
Author : Muhammad Yeasin
University of Science & Technology Chittagong ( USTC )
e-mail : gigabyte_yeasin@yahoo.com	date   : 6:59 PM 12/12/2010	uva id : 11034 Ferry Loading IV  
Bangladesh
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>

#define pb push_back
#define file freopen("in.txt","r",stdin);

using namespace std;


queue<long int> weight;
queue<int> pos;



int before_go(int current){

	if(current!=pos.front ()){
		current=pos.front ();
	}
return current;
}

int go(int current){
			
	if(current==0)
		current=1;
	else
		current=0;
return current;

}


int load(long double limit,int current){


	long double sum=0;
	sum+=weight.front();
	int test=pos.front ();
	
	while((sum<=limit)&&(test==current)&&(!weight.empty())){
	
			weight.pop();
			pos.pop();
			
			if(!weight.empty ())
				sum+=weight.front();
			
	}
return 0;
}

int main(){

	int t,len;
	char ch[7];

	
	//file
	scanf("%d",&t);
	
	long double limit;
	long int n,var;
	
	long int count;

	int current;
	int pre,ct;

	while(t--){
		
		ct=0;
		ch[0]='\x0';
		limit=0;
		current=0;
		count=0;

		scanf("%Lf%ld",&limit,&n);

		limit=limit*100.0;

		int i;
		for(i=0;i<n;i++){

				scanf("%ld%s",&var,&ch);
				len=strlen(ch);
				ch[len]='\x0';
				if(!strcmp(ch,"left"))
					current=0;
				else 
					current=1;
				
				if(var<=limit)
					ct=1;

				weight.push(var);
				pos.push(current);

				ch[0]='\x0';
		}

		current=0;
		pre=0;

		
		
		if(ct>0)
			while(!weight.empty ()){

					
				
					current=before_go(current);
					
					if(pre!=current){
						count++;
						pre=current;
					}
					
					load(limit,current);

					
					if(!weight.empty ())
						current=go(current);

					if(pre!=current){
						count++;
						pre=current;
					}
			}
		
		if((pre==current)&&(ct>0))
			count++;

		printf("%ld\n",count);

		while((!weight.empty ())&&(!pos.empty ())){
			weight.pop();
			pos.pop();
		}
	}
return 0;
}

[sohel]

A thread on this topic already exists. Don't create a new thread if there is one already.
http://acm.uva.es/board/viewtopic.php?f=33&t=11160

[sith]

Hi

I am getting WA, why?

here is my solution

Code: Select all

AC

[brianfry713]

This code doesn't compile.

Code: Select all

Main.java:9: ')' expected
       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)
                                                                                  ^
1 error

[sith]

Sorry, my mistake

Code: Select all

AC

[brianfry713]

Input

Code: Select all

1
1 4
100 right
100 right
100 right
100 left

AC output 6

Also print a newline at the end of the final line.

[sith]

AC , Thanks

[ali osama]

Got WA !!

#include<iostream>
#include<string>
#include<queue>
using namespace std;
long long var;
string str;

int main(){
long long C, L, M, count;
cin >> C;
for (int x = 0; x < C; x++){
cin >> L >> M;
L *= 100;
queue<long long> st;
queue<string> St;
for (int y = 0; y < M; y++){
cin >> var >> str;
st.push(var);
St.push(str);
}
if (St.front() == "left"){
count = 0;
}
else{
count = 1;
}

long long sum = 0;

sum += st.front();
str = St.front();
St.pop();
st.pop();

do{
while(!st.empty() && !St.empty() && sum + st.front() <= L && St.front() == str){
sum += st.front();
St.pop();
st.pop();
}
count++;

sum = 0;
if(!St.empty() && str == St.front()){
count++;
}
if(!St.empty())
str = St.front();

}while(!st.empty());

cout << count << endl;
}

return 0;
}

[brianfry713]

Look at the I/O I posted in this thread two posts before yours.

[mehrab2603]

Getting WA
Please provide some test cases.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t;
    scanf("%d", &t);
    getchar();
    while(t--) {
        int l, m;
        scanf("%d %d", &l, &m);
        getchar();
        if(m == 0) {printf("0\n"); continue;}
        l *= 100;
        int left = 0, right = 0;
        for(int i = 0; i < m; i++) {
            int length;
            char direction[10];
            scanf("%d %s", &length, direction);
            getchar();
            if(direction[0] == 'l')
                left += length;
            else
                right += length;
        }
        int ans;
        if(left > right)
            ans = 2 * (int)ceil(left / ((double)l)) - 1;
        else
            ans = 2 * (int)ceil(right / ((double)l));
        if(ans <= 0) {
            if(left > right)
                ans = 1;
            else
                ans = 2;
        }
        else if(ans % 2 != 0) {
            int n = ((ans + 1) / 2) - 1;
            if(right - (n * l) > 0)
                ans++;
        }
        else if(ans % 2 == 0) {
            int n = ans / 2;
            if(left - (n * l) > 0)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}