java-competitive/output/Main.java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    D solver = new D();
    solver.solve(1, in, out);
    out.close();
  }

  static class D extends ChelperSolution {
    public static final int N = 11;

    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 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');
    }

    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[]>() {

          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();
    }

  }

  static interface ChelperCallable {
  }

  static class InputReader {
    private BufferedReader br;
    private StringTokenizer in;

    public InputReader(String fileName) {
      try {
        br = new BufferedReader(new FileReader(fileName));
      } catch (IOException e) {
        throw new RuntimeException(e);
      }
    }

    public InputReader(InputStream inputStream) {
      br = new BufferedReader(new InputStreamReader(inputStream));
    }

    private boolean hasMoreTokens() {
      while (in == null || !in.hasMoreTokens()) {
        String s = nextLine();
        if (s == null) {
          return false;
        }
        in = new StringTokenizer(s);
      }
      return true;
    }

    public String nextString() {
      return hasMoreTokens() ? in.nextToken() : null;
    }

    public String nextLine() {
      try {
        in = null;
        return br.readLine();
      } catch (Exception e) {
        e.printStackTrace();
        return null;
      }
    }

    public int nextInt() {
      return Integer.parseInt(nextString());
    }

  }

  static class SplittingOutputWriter extends OutputWriter {
    private final OutputWriter[] outputWriters;

    public SplittingOutputWriter(OutputWriter... outputWriters) {
      super(new OutputStream() {

        public void write(int b) throws IOException {
          for (OutputWriter outputWriter : outputWriters) {
            outputWriter.write(b);
          }
        }
      });

      this.outputWriters = outputWriters;
    }

    public void flush() {
      for (OutputWriter outputWriter : outputWriters) {
        outputWriter.flush();
      }
    }

    public void close() {
      for (OutputWriter outputWriter : outputWriters) {
        outputWriter.close();
      }
    }

  }

  static abstract class ChelperSolution implements ChelperCallable {
    public static final String LOCAL_FILE = "chelper.properties";
    public static final String SAVE_RESULT_FILE = "last_test_output.txt";
    protected final boolean local = new File(LOCAL_FILE).exists();
    protected boolean firstTest = true;
    protected InputReader in;
    protected OutputWriter out;
    protected OutputWriter debug;
    protected OutputWriter fileOut;
    protected boolean saveTestResult = true;
    protected boolean gcj = false;

    protected void init() {
      if (local) {
        debug = new OutputWriter(System.err);
        if (saveTestResult) {
          fileOut = OutputWriter.toFile(SAVE_RESULT_FILE);
        }
      } else {
        debug = new OutputWriter(new NullOutputStream());
      }
    }

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      if (firstTest) {
        init();
        precalc();
        firstTest = false;
      }

      this.in = in;
      if (local && saveTestResult) {
        this.out = new SplittingOutputWriter(out, fileOut);
      } else {
        this.out = out;
      }

      preSolve(testNumber);
      solve(testNumber);
      postSolve(testNumber);
    }

    protected void precalc() {

    }

    protected void preSolve(int testNumber) {
      if (gcj) {
        out.printf("Case #%d: ", testNumber);
      }
    }

    public abstract void solve(int testNumber);

    protected void postSolve(int testNumber) {
      out.flush();
      debug.flush();
    }

  }

  static class OutputWriter extends PrintWriter {
    public static OutputWriter toFile(String fileName) {
      try {
        return new OutputWriter(fileName);
      } catch (FileNotFoundException e) {
        throw new RuntimeException(e);
      }
    }

    public void close() {
      super.close();
    }

    public OutputWriter(String fileName) throws FileNotFoundException {
      super(fileName);
    }

    public OutputWriter(OutputStream outputStream) {
      super(outputStream, true);
    }

    public OutputWriter(Writer writer) {
      super(writer, true);
    }

  }

  static class NullOutputStream extends OutputStream {
    public void write(int b) throws IOException {
      // nothing
    }

  }
}