11034 - Ferry Loading IV

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

Moderator: Board moderators

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

11034 - Ferry Loading IV

Post by sunnycare » Mon Jul 10, 2006 9:47 am

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

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Wed Jul 12, 2006 3:06 pm

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
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Fri Jul 14, 2006 6:04 am

thanks...i know...

dik
New poster
Posts: 1
Joined: Mon Aug 28, 2006 6:03 pm

Time Limit

Post by dik » Mon Aug 28, 2006 6:12 pm

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

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

Re: Time Limit

Post by Martin Macko » Tue Aug 29, 2006 11:37 pm

dik wrote: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
New poster
Posts: 11
Joined: Wed Jun 09, 2010 2:30 pm
Location: University Of Science & Technology Chittagong (USTC) Bangladesh

why WA ? 11034 - Ferry Loading IV

Post by yeasin_acm_solver » Sun Dec 12, 2010 10:07 pm

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: why WA ? 11034 - Ferry Loading IV

Post by sohel » Mon Dec 13, 2010 2:46 am

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
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11034 - Ferry Loading IV

Post by sith » Sun Oct 21, 2012 8:56 am

Hi

I am getting WA, why?

here is my solution

Code: Select all

AC
Last edited by sith on Wed Oct 31, 2012 9:00 am, edited 1 time in total.

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

Re: 11034 - Ferry Loading IV

Post by brianfry713 » Tue Oct 23, 2012 10:52 pm

This code doesn't compile.

Code: Select all

Main.java:9: ')' expected
       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)
                                                                                  ^
1 error
Check input and AC output for thousands of problems on uDebug!

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

Re: 11034 - Ferry Loading IV

Post by sith » Sat Oct 27, 2012 7:41 pm

Sorry, my mistake :)

Code: Select all

AC
Last edited by sith on Wed Oct 31, 2012 8:59 am, edited 1 time in total.

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

Re: 11034 - Ferry Loading IV

Post by brianfry713 » Wed Oct 31, 2012 1:54 am

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.
Check input and AC output for thousands of problems on uDebug!

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

Re: 11034 - Ferry Loading IV

Post by sith » Wed Oct 31, 2012 8:59 am

AC , Thanks

ali osama
New poster
Posts: 1
Joined: Wed Apr 09, 2014 2:17 am

Re: 11034 - Ferry Loading IV

Post by ali osama » Fri Jul 18, 2014 7:18 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11034 - Ferry Loading IV

Post by brianfry713 » Fri Jul 18, 2014 9:02 pm

Look at the I/O I posted in this thread two posts before yours.
Check input and AC output for thousands of problems on uDebug!

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 11034 - Ferry Loading IV

Post by mehrab2603 » Thu Jan 01, 2015 9:57 am

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

Post Reply

Return to “Volume 110 (11000-11099)”