514 - Rails
Moderator: Board moderators
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 pm
514 - Rails : why WA?
My algorithm is to create a "stack" ,
and required permutation stored in a array named "permutation"
After input,
I check number 1 to N in a for loop
if number i entered now and the permutation need him now,
the permutation index changes to the next index and check if there are other can be pop from the stack.
finally,if stack has 0 element ->ans is Yes
else -> No
[sorry for my poor english (- -")]
-------------------------------------------------------------
and required permutation stored in a array named "permutation"
After input,
I check number 1 to N in a for loop
if number i entered now and the permutation need him now,
the permutation index changes to the next index and check if there are other can be pop from the stack.
finally,if stack has 0 element ->ans is Yes
else -> No
[sorry for my poor english (- -")]
-------------------------------------------------------------
Code: Select all
#include<iostream>
using namespace std;
int main(void)
{
int N,i,stack[1001],permutation[1001],top,per,j;
while(cin>>N&&N)
{
while(cin>>permutation[1])
{
if(permutation[1]!=0)
{
for(i=2;i<=N;i++)
cin>>permutation[i];
top = 0;
per = 1;
for(i=1;i<=N;i++)
{
if(permutation[per]==i)
{
per++;
while(permutation[per]==stack[top])
{
top--;
per++;
}
}
else
{
top++;
stack[top] = i;
}
}
if(top==0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
else
{
cout<<endl;
break;
}
}
}
return 0;
}
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
I'm sorry, your code is right.
But have one thing to attention:
if(permutation[per]==i)
{
per++;
while(permutation[per]==stack[top])
{
top--;
per++;
}
}
When you do top--;
Maybe top will come to 0!! this is why you got WA
so you can change the code to
if(permutation[per]==i)
{
per++;
while(permutation[per]==stack[top] && top>0)
{
top--;
per++;
}
}
then I think you will get AC
But have one thing to attention:
if(permutation[per]==i)
{
per++;
while(permutation[per]==stack[top])
{
top--;
per++;
}
}
When you do top--;
Maybe top will come to 0!! this is why you got WA
so you can change the code to
if(permutation[per]==i)
{
per++;
while(permutation[per]==stack[top] && top>0)
{
top--;
per++;
}
}
then I think you will get AC
514 WA
This is my code . I keep getting WA. why is that?? Can any one tell me?
Code: Select all
#include<stdio.h>
void push(int);
int pop(void);
int stack[1001]={0},top=0;
void main()
{
int noc=0;
for(;;)
{
scanf("%d",&noc);
if(noc==0)
break;
for(;;)
{
int rail[1001]={0},i,flag=0,j,diff=0,large=0,k=1,p;
scanf("%d",&rail[1]);
if(rail[1]==0)
break;
for(i=2;i<=noc;i++)
scanf("%d",&rail[i]);
for(j=0;j<noc;j++)
{
if(rail[j]<rail[j+1])
{
diff=rail[j+1]-large;
for(p=1;p<diff;p++)
push(large+(k++));
large=rail[j+1];
k=1;
}
else if(rail[j]>rail[j+1])
{
if(rail[j+1]!=pop())
{
flag=1;
break;
}
}
}
if(!flag)
printf("Yes\n");
else if(flag==1)
printf("No\n");
}
printf("\n");
}
}
void push(int data)
{
stack[++top]=data;
}
int pop()
{
int temp;
temp=stack[top];
top--;
return temp;
}
514 - Algorithm error?
Hello everyone!
I've tested my solution with tan_Yui test data and it works all right. I only make a simulation of the problem. Sorry for posting code, but really, I couldn't find the mistake.
I would be glad if some test data is sent or if someone could check the algorithm, maybe I'm forgetting somethign.
cur is the current order = 1, 2, 3, ... n
des is the desired order = a1, a2, a3, ..., an
Thanks in advance.
I've tested my solution with tan_Yui test data and it works all right. I only make a simulation of the problem. Sorry for posting code, but really, I couldn't find the mistake.
I would be glad if some test data is sent or if someone could check the algorithm, maybe I'm forgetting somethign.
cur is the current order = 1, 2, 3, ... n
des is the desired order = a1, a2, a3, ..., an
Code: Select all
String solve(Vector cur, Vector des) {
Vector st = new Vector();
Vector b = new Vector();
for (int i = 0; i < des.size(); i++) {
Integer next = (Integer) des.elementAt(i);
int idx = cur.indexOf(next);
if (idx >= 0) {
while (idx > 0) {
Integer w = (Integer) cur.elementAt(0);
cur.removeElementAt(0);
st.addElement(w);
idx--;
}
cur.removeElementAt(0);
b.addElement(next);
} else {
Integer w = (Integer) st.elementAt(st.size() - 1);
if (w.equals(next)) {
st.removeElementAt(st.size() - 1);
b.addElement(next);
} else {
return "No";
}
}
}
if (cur.size() > 0 || st.size() > 0)
return "No";
return "Yes";
}
One thing I notice is that you didn't seem to clear the contents of your stack array after you are done processing 1 line of input.
Another thing is that your code seems more complicated than needed, due to your approach. For instance, you don't really need to implement stack. (I solved this with just 2 arrays). Try to come up with a simpler approach and that might be faster than trying to debug this particular piece of code.
Another thing is that your code seems more complicated than needed, due to your approach. For instance, you don't really need to implement stack. (I solved this with just 2 arrays). Try to come up with a simpler approach and that might be faster than trying to debug this particular piece of code.
514 - Rails, why PE?
Hi.
I have submitted the solution for this problem 5 times, and every time I get a “Presentation Error”, but really don’t understand why. I format the output as it told in the problem description: “there is one empty line after the lines corresponding to one block of the input file”. And as the last “non-null” block is also a block, it also must be followed by an empty line. So having such an input:
#Beginning
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
#End
we must get this output:
#Beginning
Yes
No
Yes
#End
Note the empty line after the last answer. But written in this way, I get PE, so I’ve also tried to eliminate the last empty line, but this retrieves the same error. I can guarantee that don’t add redundant spaces anywhere. So, where am I mistaken? I’m new to this site, and I wonder if it’s possible to obtain the test case and the result, because of which PE occurs?
Thanks in advance
Anna[quote][/quote]
I have submitted the solution for this problem 5 times, and every time I get a “Presentation Error”, but really don’t understand why. I format the output as it told in the problem description: “there is one empty line after the lines corresponding to one block of the input file”. And as the last “non-null” block is also a block, it also must be followed by an empty line. So having such an input:
#Beginning
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
#End
we must get this output:
#Beginning
Yes
No
Yes
#End
Note the empty line after the last answer. But written in this way, I get PE, so I’ve also tried to eliminate the last empty line, but this retrieves the same error. I can guarantee that don’t add redundant spaces anywhere. So, where am I mistaken? I’m new to this site, and I wonder if it’s possible to obtain the test case and the result, because of which PE occurs?
Thanks in advance
Anna
Code: Select all
-
- Learning poster
- Posts: 62
- Joined: Sun Jul 09, 2006 8:31 am
- Location: University of Dhaka
- Contact:
for your input my output is
this may help u
best of luck
Code: Select all
Yes
No
<===blank line
Yes
<===blank line
<=== cursor is here
best of luck
Akash chhoyar swopno
Dream to touch the sky
Dream to touch the sky
Yea, it worked, thank you very much.Debashis Maitra wrote:for your input my output isthis may help uCode: Select all
Yes No <===blank line Yes <===blank line <=== cursor is here
best of luck
-
- Learning poster
- Posts: 53
- Joined: Sat Jul 29, 2006 7:33 am
- Location: (CSE,DU), Dhaka,Bangladesh
514(why wrong answer) plz help
#include<stdio.h>
void main()
{
int i,j,ish[1000000],ash[1000000],tot,index,count,aa,dex,k,m;
for(;;)
{
scanf("%d",&tot);
if(tot==0)
break;
for(;;)
{
index=0;dex=0;
for(i=1;i<=tot;i++)
{
scanf("%d",&ish[index=index+1]);
if(ish[index]==0)
break;
}
if(ish[index]==0)
break;
count=1;j=1;
while(count<=tot)
{
if(ish[j]!=count)
ash[dex=dex+1]=count;
if(ish[j]==count)
{
if(dex<count && j<count)
{
k=j;
for(m=dex;m>=1;m--)
{
if(ash[m]!=ish[k+1])
{
printf("No\n");
goto aa;
}
k++;
}
}
j++;
}
count++;
}
printf("Yes\n");
aa:
}
printf("\n");
}
}
void main()
{
int i,j,ish[1000000],ash[1000000],tot,index,count,aa,dex,k,m;
for(;;)
{
scanf("%d",&tot);
if(tot==0)
break;
for(;;)
{
index=0;dex=0;
for(i=1;i<=tot;i++)
{
scanf("%d",&ish[index=index+1]);
if(ish[index]==0)
break;
}
if(ish[index]==0)
break;
count=1;j=1;
while(count<=tot)
{
if(ish[j]!=count)
ash[dex=dex+1]=count;
if(ish[j]==count)
{
if(dex<count && j<count)
{
k=j;
for(m=dex;m>=1;m--)
{
if(ash[m]!=ish[k+1])
{
printf("No\n");
goto aa;
}
k++;
}
}
j++;
}
count++;
}
printf("Yes\n");
aa:
}
printf("\n");
}
}
Getting WA - someone please provide test cases or explain
I have solved the problem using a simulation using stacks. Please point out any mistake.
Thanks.
Thanks.
Code: Select all
Removing the code .. as it was giving AC
Last edited by sangram on Thu Sep 20, 2007 11:31 pm, edited 1 time in total.
Read the problem again.
Hope it helps.
But you are printing a blank line between cases. Print a blank line after each case.there is one empty line after the lines corresponding to one block of the input file
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
Blank line business not clear
Hi,
I didn't really understand what you meant.
I tried with the sample data as follows:
This produced the output as follows:
Please tell me if this is wrong.
Thanks,
Sangram
I didn't really understand what you meant.
I tried with the sample data as follows:
Code: Select all
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
5 6 4 3 2 1
1 2 3 4 5 6
0
10
1 2 3 4 5 10 9 8 7 6
0
0
Code: Select all
Yes
No
Yes
Yes
Yes
Yes
Thanks,
Sangram
Well, check the output below...
Output:
Here '^' means the newline character. Hope you understand.
Output:
Code: Select all
Yes^
No^
^
Yes^
Yes^
Yes^
^
Yes^
^
Ami ekhono shopno dekhi...
HomePage
HomePage