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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
| import java.io.*;
import java.util.*;
public class Lineup {
static ArrayList<String> restrictionsA;
static ArrayList<String> restrictionsB;
private static ArrayList<String> permutations(ArrayList<String> s ) {
// 1. finds the largest k, that c[k] < c[k+1]
int first = s.size() - 2;
for ( ; first >= 0; first-- ) {
if (s.get(first).compareTo(s.get(first + 1)) < 0)
break;
}
if (first == -1)
return null;
// 2. find last index toSwap, that c[k] < c[toSwap]
int toSwap = s.size() - 1;
for ( ; toSwap >= 0; toSwap-- ) {
if (s.get(first).compareTo(s.get(toSwap)) < 0)
break;
}
// 3. swap elements with indexes first and last
Collections.swap(s, first++, toSwap);
// 4. reverse sequence from k+1 to n (inclusive)
toSwap = s.size() - 1;
while ( first < toSwap )
Collections.swap( s, first++, toSwap-- );
return s;
}
private static int findIndex(ArrayList<String> perm, String cow) {
for (int i = 0; i < perm.size(); i++) {
if (cow.equals(perm.get(i))) {
return i;
}
}
return -1;
}
private static boolean check(ArrayList<String> perm) {
boolean passed = true;
for (int i = 0; i < restrictionsA.size() ; i++) {
String cow1 = restrictionsA.get(i);
String cow2 = restrictionsB.get(i);
int a = findIndex(perm, cow1);
int b = findIndex(perm, cow2);
if (Math.abs(a - b) != 1) {
passed = false;
break;
}
}
if (passed) {
return true;
}
else {
return false;
}
}
public static void main(String[] args) throws IOException {
Lineup.Kattio io = new Lineup.Kattio("lineup");
int N = io.nextInt();
ArrayList<String> cows = new ArrayList<String>(
Arrays.asList("Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"));
restrictionsA = new ArrayList<String>();
restrictionsB = new ArrayList<String>();
for (int i = 0; i < N; i++) {
String a = io.next();
io.next();
io.next();
io.next();
io.next();
String b = io.next();
restrictionsA.add(a);
restrictionsB.add(b);
}
Collections.sort(cows);
while (cows != null) {
if (check(cows)) {
for(String c : cows) {
io.println(c);
}
break;
}
cows = permutations(cows);
}
io.close();
}
// https://usaco.guide/general/io?lang=java#io-template
static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName + ".out"));
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) {}
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}
|