## 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

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;
while(cases-->0)
{
cin>>l;
l*=100;
cin>>m;
cnt=0;
curSide='l';
s=0;

while(m-->0)
{
cin>>cl>>side;
if(side!=curSide)
{
cnt++;
curSide=side;
s=cl;
}
else
{
if(s+cl>l)
{
cnt+=2;
s=cl;
}
else
{
s+=cl;
}
}
}
if(s!=0)
cnt++;
cout<<cnt<<endl;
}
}
``````
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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
thanks...i know...
dik
New poster
Posts: 1
Joined: Mon Aug 28, 2006 6:03 pm

### Time Limit

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Time Limit

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

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;

//file
scanf("%d",&t);

long double limit;
long int n,var;

long int count;

int current;
int pre,ct;

while(t--){

ct=0;
ch='\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='\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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: why WA ? 11034 - Ferry Loading IV

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

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

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

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

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

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

### Re: 11034 - Ferry Loading IV

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

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

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;
scanf("%d %s", &length, direction);
getchar();
if(direction == '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;
}
``````