514 - Rails

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

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

514 - Rails

Post by yahoo » Mon Aug 05, 2002 8:15 pm

I can't understand why my this program gives wrong answer. I think my algorithm is ok. Is there anything i miss? Please kindly check my code and tell me where i am wrong. thanks in advance.
#include <stdio.h>

main()
{
int a[1000],cnt,count,i,k,j,n,flag,flag2;
while(1)
{
scanf("%d",&n);
if(n==0) break;

for(i=0;i<n;i++)
a[i]=0;
while(1)
{
i=0;
scanf("%d",&a[i]);
if(a[i]==0) break;
for(i=1;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]==0) break;
}
a[i]=0;
cnt=flag=flag2=0;
for(j=0;j<n;j++)
{
if(a[j]<a[j+1]) cnt++;
else break;
}
if(cnt==n-1) {flag=1;printf("Yes\n");}
if(!flag)
{
count=0;
for(k=0;k<n;k++)
{
if(a[k]>a[k+1]) count++;
else break;
}
if(count==n) {flag2=1;printf("Yes\n");}
}
if(!flag && !flag2) printf("No\n");
}
printf("\n");
}
return 0;
}

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

What is the algorithm

Post by sayeed » Wed Aug 07, 2002 9:04 pm

It seems strange . What is the algorithm of that probelm ? I tried in a similar way but got wa. Will someone explain the algorithm?

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Mar 19, 2003 7:03 pm

I got WA too. don't understand why... help me please :(
here i give my code:
[c]
#include <stdio.h>

int ara[1001];
int top, N;

void push(int n)
{
ara[++top] = n;
}

int pop()
{
return ara[top--];
}

void main()
{
int ara1[1001], ara2[1001];
int i, j, n1, n2, f = 0;

while(1==scanf("%d", &N) && N)
{
if(f)
printf("\n");
else
f = 1;

while(1)
{
scanf("%d", &ara1[0]);
if(!ara1[0]) break;
for(i=1; i<N; i++) scanf("%d", &ara1);

top = -1; /* initialize the stack */

for(i=0, j=0; i<N; i++)
{
n1 = ara1[j];
n2 = i+1;
if(n1!=n2)
{
push(n2);
}
else
{
ara2[j++] = n2;
}
}

while(top>=0)
ara2[j++] = pop();

for(i=0; i<N; i++)
if(ara1!=ara2)
break;

if(i < N)
printf("No\n");
else
printf("Yes\n");
}
}
}
[/c]

Sarwar
New poster
Posts: 3
Joined: Tue Nov 04, 2003 12:20 pm
Location: Dhaka

WA too

Post by Sarwar » Tue Nov 04, 2003 12:26 pm

I am getting WA, please help.

Here is my code:

[cpp]
#include<stdio.h>
int top,a[1002];
void push(int p)
{
a[top++]=p;
}
int pop()
{ int p;
top--;
return a[top];
}
int main()
{
int b[1002],n,m,i,c,count=1,v,k;
while(1)
{
top=0;
v=1;
scanf("%d",&n);if(n==0)break;
while(1)
{
top=0;
for(i=0;i<n;i++)
{
scanf("%d",&b);
if(b[0]==0){v=0;break;}
}
if(v==0)break;
count=1;
for(i=0;count<=n;)
{
if(count==b){i++;count++;}
else {push(count);count++;}
}
c=i;
while(c<=n)
{
if(b[c]!=pop())break;
c++;
}
if(c==n)printf("Yes\n");
else printf("No\n");
}
}
return 0;
}

[/cpp]

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

514 wa

Post by Yu Fan » Thu Nov 13, 2003 4:03 am

#include <iostream>
using namespace std;
int main()
{
unsigned i,n,require,train,rf;
int flag;
unsigned *station;
unsigned ans[999];
int t=0;
while(cin>>n!=0) {
flag=-1;
rf=0;
train=1;
station=new unsigned[n+2];
while(cin>>require!=0) {
rf++;
if(require<train) {
if(require!=station[flag]) {
ans[t++]=0;
for(;rf<n;rf++)
cin>>require;
}
else
flag--;
}
else if(require==train)
train++;
else {
for(train=train;train<require;train++)
station[++flag]=train;
train++;
}
if(train>n) {
rf=0;
ans[t++]=1;
for(train=0;train<n+1;train++)
station[train]=0;
train=1;
flag=-1;
}
}
ans[t++]=2;
delete[]station;
}
for(i=0;i<t;i++) {
if(ans==0)
cout<<"No"<<endl;
else if(ans==1)
cout<<"Yes"<<endl;
else
cout<<endl;
}
return 0;
}



tell me what wrong with it...

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Fri Nov 14, 2003 6:43 pm

hmm funny. I've tried to compile your code on my machine.
And it didn't produce output even on the sample input
test cases.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Fri Nov 14, 2003 6:46 pm

hmm funny. I've tried to compile your code on my machine.
And it didn't produce output even on the sample input
test cases. It keeps asking for input even though
I keep inputing 0.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

514 WA why?

Post by mohiul alam prince » Tue Sep 28, 2004 12:36 pm

what is my problem
- i have used two queue A & B
- 1 stake S

just i have do push & pop
this is my function
[cpp]
function () {
while ( 1 ) {

if ( A.size() ) {
S.push( A.front() );
A.pop();
}
x = S.top();
y = B.front();
if ( x == y ) {
S.pop();
B.pop();
}
else if ( !A.size() ) {
printf("No\n");
return ;
}
if ( !B.size() ) {
printf("Yes\n");
return ;
}
}
printf("No\n");
}
[/cpp]

please give me some input
or some hints

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

Post by sohel » Tue Sep 28, 2004 1:07 pm

mohiul wrote: what is my problem
- i have used two queue A & B
- 1 stake S
May be that's where you are wrong. Using Queues will not lead you to the right direction. :x

And what do you mean by stake. :-?

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Sep 28, 2004 1:46 pm

sohel wrote
May be that's where you are wrong. Using Queues will not lead you to the right direction.
sorry for my mistake this is stack

but i can not understand what is my mistake
can u explain me ?[/quote]

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

514

Post by Heartattack! » Tue Nov 30, 2004 10:56 am

This seems a very easy problem. Are there special cases? Can there be illegal numbers in the input [like if n=1 can a number in the permutation be 3]? I've tried all sorts of cases but I keep getting WA. Could someone please take a kind look at my code?
[cpp]
// p514.Rails.cpp : Defines the entry point for the console application.
//

@begin_of_source_code

/* @JUDGE_ID: ******* 514 C++ */

#include "iostream"
#include "stack"
using namespace std;
void main()
{
stack<int> station;
int train,n,in,dummy,done;
bool flag,act;

while(1)
{
inn:
cin>>n;
if(!n)
break;
while(1)
{
train=1;
flag=1;
done=0;
for(int i=0;i<n;++i)
{
cin>>in;
++done;

if(!in)
if(station.empty())
{
cout<<endl;
goto inn;
}
if(in==train)
{
++train;
continue;
}
if(in>train)
{
while(in>train)
{
station.push(train);
++train;
if(train>n)
{
flag =0;
goto print;
}
}
continue;
}
if(in<train)
{
if(in==station.top())
{
station.pop();
continue;
}
else
{
flag=0;
goto print;
}
}
}
print:
if(flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
while(!station.empty())
station.pop();
done=n-done;
while(done--)
cin>>in;
}
}
}
@end_of_source_code


[/cpp]

Thanks in advance.
PS: A bit of explanation:
n=number of trains
train=number of the trains which has not yet come into the station
done=number of inputs processed[used to clear n-done inputs]
flag=bool to see if posiible or not
station=the station stack



BTW, can the input be like this:
5
5 5 4 4 3

I mean, can it include repeated numbers or numbers out of the range of n?
Can it be like this:
5
1 2 3 4 5 6 7
0

Can there be 0s in the inputs like:
5
1 0 2 3 4
Please guys, this is blowing my head open. It seems so simple.... :oops:
We will, We will BREAK LOOP!!!!

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Fri Jan 21, 2005 1:44 pm

you dont have to check for any such improper cases.

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: p514 WA

Post by nnahas » Fri Jan 21, 2005 4:38 pm

Your program returns No on this permutation:
1 2 3 4 5 10 9 8 7 6

If I understood the problem correctly, it should return Yes:
the first 5 coaches leave the station first in first out and the last five Last in First out , so it should return yes.

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

514

Post by sunnycare » Thu Apr 28, 2005 3:02 am

my algo is just to simulate ....

my code here:

Code: Select all

//514 Rails

#include <queue>
#include <iostream>
#include <stack>
using namespace std;

int main(int argc,char *argv[])
{
    queue<int> src;
    queue<int> dst;
    stack<int> st;
    int n,tmp,i,dstTop;
    bool r;
    cin>>n;
    while(n!=0)
    {
        //clear the queue and stack
        while(!src.empty())
        	src.pop();
       	while(!dst.empty())
       		dst.pop();
  		while(!st.empty())
  			st.pop();
        
        cin>>tmp;
        while(tmp!=0)
        {
            r=true;
            dst.push(tmp);
            src.push(1);
            for(i=2;i<=n;i++)
           	{
           	    cin>>tmp;
           	    dst.push(tmp);
           	    src.push(i);
           	}
           	for(i=1;i<=n;i++)
           	{
           	    dstTop=dst.front();
           	    while(!src.empty())
           	    {
           	        if(src.front()<=dstTop)
           	        {
                        tmp=src.front();
                        src.pop();
                        st.push(tmp);
                    }
                    else
                    	break;    
           	        
           	    }
                if(st.top()==dstTop)
                {
                    st.pop();
                }
                else
                {
                    r=false;
                    break;
                }
                dst.pop();
            }
            if(r)
            	cout<<"Yes";
           	else
           		cout<<"No";
      		cout<<endl;
            cin>>tmp;
        }
        cout<<endl;
        cin>>n;
    }
}                       

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: prog 514 WA need sample input or check my algo thanks

Post by tan_Yui » Sat Jun 04, 2005 11:08 am

Hi, sunnycare and everyone.
Following input may help you for debugging. :)

Input :

Code: Select all

5
1 2 3 4 5
5 4 1 2 3
1 4 3 2 5
3 4 2 5 1
3 4 2 1 5
4 3 5 2 1
0
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
0
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
0
10
5 7 10 9 8 6 4 3 2 1
5 6 4 8 7 3 2 9 1 10
0
0
Output :

Code: Select all

Yes
No
Yes
Yes
Yes
Yes

Yes
Yes
Yes
Yes
No
Yes

Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
No
No
No
No
Yes

Yes
Yes

Best regards.

Post Reply

Return to “Volume 5 (500-599)”