NEERC/funny/funny_rs_tl.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class funny_rs_tl implements Runnable {
   5     private BufferedReader in;
   6     private PrintWriter out;
   7     private int[][] w;
   8     private int[] cur;
   9     private boolean[][] mark;
  10     private int n, m;
  11     private Set<String> answer, originalWords;
  12
  13     private void check(boolean expr, String msg) {
  14         if (!expr) {
  15             throw new Error(msg);
  16         }
  17     }
  18
  19     private void checkBounds(int n, int low, int hi, String nStr) {
  20         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  21     }
  22
  23     private void gen(int minWords, int pos) {
  24         if (pos == 26) {
  25             int good = 0;
  26             for (int i = 0; i < m; i++) {
  27                 if (mark[pos][i]) {
  28                     good++;
  29                 }
  30             }
  31             if (good > minWords) {
  32                 return;
  33             }
  34             genWords("");
  35             return;
  36         }
  37         for (int u = 0; ; u++) {
  38             cur[pos] = u;
  39             int good = 0;
  40             for (int i = 0; i < m; i++) {
  41                 mark[pos + 1][i] = mark[pos][i] && (w[i][pos] >= u);
  42                 if (mark[pos + 1][i]) {
  43                     good++;
  44                 }
  45             }
  46             if (good < minWords) {
  47                 break;
  48             }
  49             gen(minWords, pos + 1);
  50             if (answer.size() == n) {
  51                 break;
  52             }
  53         }
  54     }
  55
  56     private void genWords(String prefix) {
  57         if (answer.size() == n) {
  58             return;
  59         }
  60         boolean found = false;
  61         for (int i = 0; i < 26; i++) {
  62             if (cur[i] > 0) {
  63                 cur[i]--;
  64                 genWords(prefix + (char) ('A' + i));
  65                 cur[i]++;
  66                 found = true;
  67             }
  68         }
  69         if (!found) {
  70             if (prefix.length() > 0 && !originalWords.contains(prefix)) {
  71                 answer.add(prefix);
  72             }
  73         }
  74     }
  75
  76     private void solve() throws IOException {
  77         StringTokenizer st = new StringTokenizer(in.readLine());
  78         n = Integer.parseInt(st.nextToken());
  79         m = Integer.parseInt(st.nextToken());
  80         checkBounds(n, 1, 100, "n");
  81         checkBounds(m, 1, 1000, "m");
  82         w = new int[m][26];
  83         originalWords = new HashSet<String>();
  84         for (int i = 0; i < m; i++) {
  85             String line = in.readLine();
  86             originalWords.add(line);
  87             check(line.length() <= 100, "word length > 100");
  88             for (int j = 0; j < line.length(); j++) {
  89                 int ch = line.charAt(j) - 'A';
  90                 check((0 <= ch) && (ch < 26), "Invalid chars");
  91                 w[i][ch]++;
  92             }
  93         }
  94
  95         mark = new boolean[27][m];
  96         cur = new int[26];
  97         answer = new HashSet<String>();
  98         for (int i = m; i >= 0; i--) {
  99             if (answer.size() < n) {
 100                 Arrays.fill(mark[0], true);
 101                 gen(i, 0);
 102             }
 103         }
 104         for (String w: answer) {
 105             out.println(w);
 106         }
 107     }
 108
 109     public static void main(String[] args) {
 110         new Thread(new funny_rs_tl()).start();
 111     }
 112
 113     public void run() {
 114         String problem = getClass().getName().split("_")[0];
 115         try {
 116             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 117             out = new PrintWriter(new File(problem + ".out"));
 118             solve();
 119             in.close();
 120             out.close();
 121         } catch (IOException e) {
 122             e.printStackTrace();
 123             System.exit(1);
 124         }
 125     }
 126 }