514 - Rails
Moderator: Board moderators
514 - Rails
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;
}
#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;
}
What is the algorithm
It seems strange . What is the algorithm of that probelm ? I tried in a similar way but got wa. Will someone explain the algorithm?
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]
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]
WA too
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]
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]
514 wa
#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...
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...
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
514 WA why?
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
- 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
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
-
- New poster
- Posts: 45
- Joined: Fri Jan 16, 2004 7:02 pm
- Location: CSE::BUET
- Contact:
514
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....
[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....
We will, We will BREAK LOOP!!!!
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
Re: p514 WA
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.
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.
514
my algo is just to simulate ....
my code here:
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;
}
}
Re: prog 514 WA need sample input or check my algo thanks
Hi, sunnycare and everyone.
Following input may help you for debugging.
Input :
Output :
Best regards.
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
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