悟云

火车进站

题目描述

1
给定一个正整数N代表火车数量,0<N<10,接下来输入火车入站的序列,一共N辆火车,每辆火车以数字1-9编号,火车站只有一个方向进出,同时停靠在火车站的列车中,只有后进站的出站了,先进站的才能出站。要求以字典序排序输出火车出站的序列号。

输入描述

1
有多组测试用例,每一组第一行输入一个正整数N(0<N<10),第二行包括N个正整数,范围为1到9。

输出描述

1
输出以字典序从小到大排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行,具体见sample。

示例

输入

1
2
3
1 2 3

输出

1
2
3
4
5
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package main
import (
"fmt"
"sort"
"strings"
)
type stack []string
func (s *stack) push(v string) {
*s = append(*s, v)
}
func (s *stack) pop() string {
l := len(*s)
result := (*s)[l-1]
*s = (*s)[0 : l-1]
return result
}
func (s *stack) unshift() string {
result := (*s)[0]
*s = (*s)[1:]
return result
}
func (s *stack) empty() bool {
return len(*s) == 0
}
func main() {
for {
var N uint8
_, err := fmt.Scan(&N)
if err != nil {
break
}
var trainList = make([]string, 0, N)
for i := uint8(0); i < N; i++ {
var train string
fmt.Scan(&train)
trainList = append(trainList, train)
}
pre := stack(trainList)
in := stack{}
out := stack{}
handle(pre, in, out)
}
sort.Strings(results)
for _, result := range results {
fmt.Println(result)
}
}
var (
results []string
)
func handle(pre, in, out stack) {
if pre.empty() && in.empty() {
results = append(results, strings.Join(out, " "))
return
}
if !pre.empty() {
prec := make([]string, len(pre))
inc := make([]string, len(in))
outc := make([]string, len(out))
copy(prec, pre)
copy(inc, in)
copy(outc, out)
pres := stack(prec)
ins := stack(inc)
outs := stack(outc)
ins.push(pres.unshift())
handle(pres, ins, outs)
}
if !in.empty() {
prec := make([]string, len(pre))
inc := make([]string, len(in))
outc := make([]string, len(out))
copy(prec, pre)
copy(inc, in)
copy(outc, out)
pres := stack(prec)
ins := stack(inc)
outs := stack(outc)
outs.push(ins.pop())
handle(pres, ins, outs)
}
}