NEERC/funny/funny_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class funny_rs implements Runnable {
   5         private BufferedReader in;
   6         private PrintWriter out;
   7         private int[][] w;
   8         private int n, m;
   9         private Set<String> answer, originalWords;
  10
  11         private void check(boolean expr, String msg) {
  12                 if (!expr) {
  13                         throw new Error(msg);
  14                 }
  15         }
  16
  17         private void checkBounds(int n, int low, int hi, String nStr) {
  18                 check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  19         }
  20
  21         private class Combination implements Comparable<Combination> {
  22                 public int[] letters;
  23                 public int count, hash;
  24
  25                 public Combination(int[] letters) {
  26                         this.letters = new int[26];
  27                         for (int i = 0; i < 26; i++) {
  28                                 this.letters[i] = letters[i];
  29                         }
  30
  31                         count = 0;
  32                         LOOP:
  33                         for (int i = 0; i < m; i++) {
  34                                 for (int j = 0; j < 26; j++) {
  35                                         if (w[i][j] < letters[j]) {
  36                                                 continue LOOP;
  37                                         }
  38                                 }
  39                                 count++;
  40                         }
  41
  42                         hash = 0;
  43                         for (int i = 0; i < 26; i++) {
  44                                 hash ^= (letters[i] << i);
  45                         }
  46                 }
  47
  48                 public void genWords(String prefix) {
  49                         if (answer.size() == n) {
  50                                 return;
  51                         }
  52                         boolean found = false;
  53                         for (int i = 0; i < 26; i++) {
  54                                 if (letters[i] > 0) {
  55                                         letters[i]--;
  56                                         genWords(prefix + (char) ('A' + i));
  57                                         letters[i]++;
  58                                         found = true;
  59                                 }
  60                         }
  61                         if (!found) {
  62                                 if (prefix.length() > 0 && !originalWords.contains(prefix)) {
  63                                         answer.add(prefix);
  64                                 }
  65                         }
  66                 }
  67
  68                 @Override
  69                 public int compareTo(Combination that) {
  70                         return that.count - count;
  71                 }
  72
  73                 @Override
  74                 public boolean equals(Object o) {
  75                         Combination that = (Combination) o;
  76                         for (int i = 0; i < letters.length; i++) {
  77                                 if (letters[i] != that.letters[i]) {
  78                                         return false;
  79                                 }
  80                         }
  81                         return true;
  82                 }
  83
  84                 @Override
  85                 public int hashCode() {
  86                         return hash;
  87                 }
  88         }
  89
  90         private void solve() throws IOException {
  91                 StringTokenizer st = new StringTokenizer(in.readLine());
  92                 n = Integer.parseInt(st.nextToken());
  93                 m = Integer.parseInt(st.nextToken());
  94                 checkBounds(n, 1, 100, "n");
  95                 checkBounds(m, 1, 1000, "m");
  96                 w = new int[m][26];
  97                 originalWords = new HashSet<String>();
  98                 for (int i = 0; i < m; i++) {
  99                         String line = in.readLine();
 100                         originalWords.add(line);
 101                         check(line.length() <= 100, "word length > 100");
 102                         for (int j = 0; j < line.length(); j++) {
 103                                 int ch = line.charAt(j) - 'A';
 104                                 check((0 <= ch) && (ch < 26), "Invalid chars");
 105                                 w[i][ch]++;
 106                         }
 107                 }
 108
 109                 PriorityQueue<Combination> queue = new PriorityQueue<Combination>();
 110                 Set<Combination> visited = new HashSet<Combination>();
 111
 112                 Combination start = new Combination(new int[26]);
 113                 queue.add(start);
 114                 visited.add(start);
 115                 answer = new HashSet<String>();
 116                 while (answer.size() < n) {
 117                         Combination cur = queue.poll();
 118                         cur.genWords("");
 119                         for (int i = 0; i < 26; i++) {
 120                                 cur.letters[i]++;
 121                                 Combination newCur = new Combination(cur.letters);
 122                                 cur.letters[i]--;
 123                                 if (visited.contains(newCur)) {
 124                                         continue;
 125                                 }
 126                                 queue.add(newCur);
 127                         }
 128                 }
 129
 130                 for (String w: answer) {
 131                         out.println(w);
 132                 }
 133         }
 134
 135         public static void main(String[] args) {
 136                 new Thread(new funny_rs()).start();
 137         }
 138
 139         public void run() {
 140                 String problem = getClass().getName().split("_")[0];
 141                 try {
 142                         in = new BufferedReader(new FileReader(new File(problem + ".in")));
 143                         out = new PrintWriter(new File(problem + ".out"));
 144                         solve();
 145                         in.close();
 146                         out.close();
 147                 } catch (IOException e) {
 148                         e.printStackTrace();
 149                         System.exit(1);
 150                 }
 151         }
 152 }