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

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

Post by sunnycare » Wed Jun 08, 2005 4:18 am

thanks
finally got ac

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

514 - Rails : why WA?

Post by Hector_Hsu » Wed Feb 01, 2006 8:02 am

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 (- -")]
-------------------------------------------------------------

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

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Feb 05, 2006 9:51 am

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

Sayeef
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

514 WA

Post by Sayeef » Sun Sep 03, 2006 12:22 pm

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

icesoft85
New poster
Posts: 4
Joined: Sun Mar 26, 2006 5:51 am
Contact:

514 - Algorithm error?

Post by icesoft85 » Thu Sep 14, 2006 12:51 am

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

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";
	}
Thanks in advance.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Nov 09, 2006 8:03 am

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.

annag
New poster
Posts: 2
Joined: Tue Jan 16, 2007 9:21 pm

514 - Rails, why PE?

Post by annag » Tue Jan 16, 2007 9:31 pm

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]

User avatar
Debashis Maitra
Learning poster
Posts: 62
Joined: Sun Jul 09, 2006 8:31 am
Location: University of Dhaka
Contact:

Post by Debashis Maitra » Wed Jan 17, 2007 7:20 pm

for your input my output is

Code: Select all

Yes
No
       <===blank line
Yes
       <===blank line
<=== cursor is here 

this may help u

best of luck
Akash chhoyar swopno
Dream to touch the sky

annag
New poster
Posts: 2
Joined: Tue Jan 16, 2007 9:21 pm

Post by annag » Thu Jan 18, 2007 12:22 am

Debashis Maitra wrote:for your input my output is

Code: Select all

Yes
No
       <===blank line
Yes
       <===blank line
<=== cursor is here 

this may help u

best of luck
Yea, it worked, thank you very much.

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

514(why wrong answer) plz help

Post by ishtiaq ahmed » Wed Jan 24, 2007 6:25 am

#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");
}
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Jan 24, 2007 6:41 am

Search first..
Don't open a new thread if there is one already

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

Getting WA - someone please provide test cases or explain

Post by sangram » Wed Sep 19, 2007 2:21 pm

I have solved the problem using a simulation using stacks. Please point out any mistake.

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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 20, 2007 8:37 am

Read the problem again.
there is one empty line after the lines corresponding to one block of the input file
But you are printing a blank line between cases. Print a blank line after each case.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

Blank line business not clear

Post by sangram » Thu Sep 20, 2007 11:46 am

Hi,
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
This produced the output as follows:

Code: Select all

Yes
No

Yes
Yes
Yes

Yes
Please tell me if this is wrong.

Thanks,
Sangram

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 20, 2007 11:53 am

Well, check the output below...

Output:

Code: Select all

Yes^
No^
^
Yes^
Yes^
Yes^
^
Yes^
^
Here '^' means the newline character. Hope you understand.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 5 (500-599)”