Train Problem I

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 75 Accepted Submission(s) : 23

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.

Input

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

Output

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.

Sample Input

3 123 321
3 123 312

Sample Output

Yes.
in
in
in
out
out
out
FINISH
No.
FINISH

Hint

Hint
For the first Sample Input, we let train 1 get in, then train 2 and train 3.
So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1.
In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3.
Now we can let train 3 leave.
But after that we can't let train 1 leave before train 2, because train 2 is at the top of the railway at the moment.
So we output "No.".

Author

Ignatius.L

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
    string in,out;
    
    int num;
    while(scanf("%d",&num)!=EOF)
    {
        int record[25];//记录火车进出信息
        int qwe=0;//代替序号
        cin>>in>>out;
        int innum=0;
        int outnum=0;//记录对比到第几位
        stack<char> s;
        s.push(in[innum++]);
        record[qwe++]=1;
        int as=0;
        while(as++<num*2&&innum!=outnum)//最多比较2*num次
        {
            if(!s.empty()&&s.top()==out[outnum])//判断站有没有空 站顶与输出位置是否相同
            {
                s.pop();
                outnum++;
                record[qwe++]=0;
                if(s.empty()&&innum<num)//判断站有没有空 且 火车 进完 站没有
                {
                    s.push(in[innum++]);
                    record[qwe++]=1;
                    
                
                }
                continue;
                
            }

            else
                if(s.top()!=out[outnum])//站顶与输出位置不相同 火车进站
            {
                if(innum<num)//进站 火车没用完
                {
                    s.push(in[innum++]);
                    record[qwe++]=1;
                }
                else 
                {
                    if(!s.empty()&&outnum<num)//如果火车用完了 且 站不为空 且 火车没有出完 
                                               // 就代表卡死了 火车出不来
                        break;
                
                }
            
            }
            
            
        
        }
        if(outnum<num&&!s.empty())
        {
            printf("No.
FINISH
");
        
        }
        else
        {
            printf("Yes.
");
            for(int we=0;we<qwe;we++)
            {
                if(record[we]==0)
                {
                    printf("out
");
                }
                else 
                {
                    printf("in
");
                
                }
            
            }

            printf("FINISH
");
        
        }




    
    
    
    
    }

    return 0;
}

思路：

第一辆火车进站如果如输出序列的头火车不同

就下一辆火车进栈；

如果栈顶火车与输出序列头火车相同则说明这火车要出

如果火车进完了而且栈顶火车与输出序列不同就说明这辆火车出不来

俗称卡死；

这里要记录比较次数最多是 2*火车数还要记录火车进栈数和输出序列头与栈顶火车的相同次数

如果栈顶火车与输出序列头相同则火车出栈输出序列换头火车

输出序列可以用队列存储

栈顶火车与队头相同火车出栈队列出队；

如果栈为空且队列为空这成功；

如果所有火车都进过栈队列不为空则失败