109 lines
2.2 KiB
Java
109 lines
2.2 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.Collections;
|
|
import java.util.Comparator;
|
|
import java.util.List;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import solutions.ChelperSolution;
|
|
|
|
|
|
public class D extends ChelperSolution {
|
|
|
|
@Override
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
super.solve(testNumber, in, out);
|
|
}
|
|
|
|
boolean[] merge(boolean[] a, boolean[] b) {
|
|
int n = a.length;
|
|
int m = b.length;
|
|
|
|
boolean[] c = new boolean[n + m + 2];
|
|
|
|
c[0] = true;
|
|
for (int i = 0; i < n; i++) {
|
|
c[1 + i] = a[i];
|
|
}
|
|
c[n + 1] = false;
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
c[n + 2 + i] = b[i];
|
|
}
|
|
|
|
return c;
|
|
}
|
|
|
|
public static final int N = 11;
|
|
|
|
public void rawPrint(boolean[] a) {
|
|
// for (boolean i : a) {
|
|
// out.print(i ? '(' : ')');
|
|
// }
|
|
// out.println();
|
|
for (boolean i : a) {
|
|
System.out.write(i ? '(' : ')');
|
|
}
|
|
System.out.write('\n');
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
List<List<boolean[]>> dp = new ArrayList<>();
|
|
|
|
for (int i = 0; i <= N; i++) {
|
|
dp.add(new ArrayList<>());
|
|
}
|
|
|
|
dp.get(0).add(new boolean[0]);
|
|
|
|
for (int i = 1; i <= N; i++) {
|
|
for (int l1 = 0; l1 <= i - 1; l1++) {
|
|
int l2 = i - 1 - l1;
|
|
|
|
List<boolean[]> dp1 = dp.get(l1);
|
|
List<boolean[]> dp2 = dp.get(l2);
|
|
|
|
for (boolean[] a : dp1) {
|
|
for (boolean[] b : dp2) {
|
|
dp.get(i).add(merge(a, b));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i <= N; i++) {
|
|
Collections.sort(dp.get(i), new Comparator<boolean[]>() {
|
|
@Override
|
|
public int compare(boolean[] o1, boolean[] o2) {
|
|
for (int i = 0; i < o1.length; i++) {
|
|
if (o1[i] && !o2[i]) {
|
|
return -1;
|
|
}
|
|
if (!o1[i] && o2[i]) {
|
|
return 1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
});
|
|
|
|
// out.println(i + ":");
|
|
// out.println(dp.get(i).size());
|
|
// for (boolean[] a : dp.get(i)) {
|
|
// rawPrint(a);
|
|
// }
|
|
}
|
|
|
|
int n = in.nextInt();
|
|
for (boolean[] b : dp.get(n)) {
|
|
rawPrint(b);
|
|
}
|
|
|
|
System.out.flush();
|
|
}
|
|
}
|