Moderator: Board moderators

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

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

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

Code: Select all

``````/*
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
*/

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

}

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

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

http://acm.uva.es/board/viewtopic.php?f=33&t=11160

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

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

This code doesn't compile.

Code: Select all

``````Main.java:9: ')' expected
^
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

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

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

AC , Thanks

ali osama
New poster
Posts: 1
Joined: Wed Apr 09, 2014 2:17 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

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

Getting WA 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;
}
``````