So, lets discuss the problem statement 1st and then we will head towards the possible solution.
The train entering the station has length N and is numbered in increasing order, meaning coach number 1 enters the station first and coach N enters last. At any time you can take some of the coaches already in the station and have them leave towards B, this can reorder the train. If no reordering takes place the train will leave the station with coach N first and coach 1 last (last in, first out). The order that is requested is in the input file, the first coach in the requested order is named a1 and the last one aN, from the example: Train of length 5 in order 1 2 3 4 5 (meaning a1 = 1, a2 = 2 etc): This is possible by taking each coach on it's own into the station and leave right away. This will preserve the order of the train. Train of length 5 in order 5 4 1 2 3 (a1 = 5, a2 = 4, a3 = 1 etc): If coach 5 has to leave the station first you must take every coach from number 1 till 5 into the station, now you can have 5 and 4 leave but the next coach will be number 3 while 1 is requested. This means the requested order is impossible. The solution has become clear from the last example: If the first requested number is a1 you have to put all coaches from 1 till a1 into the station and disconnect the train. Then you have a1 leave towards B and check the next requested number, if it's higher than a1 you put all coaches till that number into the station and then you have that coach leave from the station. If your station is empty at the end the requested order was possible and you should print "Yes". Putting a coach into the station is called the "push" and taking it out is the "pop", the station is your collection and the coaches are your elements that are being added to the collection. hope this will help to solve the problem. Now lets think of the solution. The accepted code is given as follows:
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node *next;
}*new_node;
struct head
{
int count;
struct node *next;
}*Head;
void create_head()
{
Head = new head();
Head->count = 0;
Head->next = NULL;
}
void create_node(int d)
{
new_node = new node();
new_node->next = NULL;
new_node->data = d;
}
void push(int d)
{
create_node(d);
if(Head==NULL)
{
Head->next = new_node;
}
else
{
new_node->next = Head->next;
Head->next = new_node;
}
Head->count++;
}
void pop()
{
struct node *temp;
temp = Head->next;
Head->next = temp->next;
free(temp);
Head->count--;
}
bool emty()
{
if(Head->count==0)
{
return true;
}
else
{
return false;
}
}
int top()
{
return Head->next->data;
}
int main()
{
int n;
while(cin>>n && n!=0)
{
while(1)
{
create_head();
int a[2000], flag=0;
bool arr[2000]={0};
for(int j=0;j<n;j++)
{
cin>>a[j];
if(a[0]==0)
{
flag=1;
break;
}
}
if( flag==1 )
{
cout<<endl;
break;
}
for(int k=0;k< n;)
{
if(emty())
{
if(k==0)
{
for(int l=1;l<=a[k];l++)
{
if(arr[l]==0)
push(l);
arr[l] = 1;
}
}
else
{
for(int l= a[k-1]+1;l<=a[k];l++)
{
if(arr[l]==0)
push(l);
arr[l] = 1;
}
}
}
else
{
if(top()==a[k])
{
pop();
k++;
}
else
{
int m = top();
if( m <a[k] )
{
for(int i=m+1; i<=a[k];i++)
{
if(arr[i]==0)
{
push(i);
}
arr[i]=1;
}
}
else
{
break;
}
}
}
}
if(emty())
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
}
return 0;
}
No comments:
Post a Comment