NEERC/funny/funny_ia.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * @author Iskander Akishev
   6  */
   7 public class funny_ia implements Runnable {
   8
   9         private static final String FILE_NAME = "funny";
  10         private int[][] w;
  11         private TreeSet<String> words;
  12         private TreeSet<NewWord> newWords;
  13         private int lim;
  14         private int n;
  15         private int m;
  16
  17         public void run() {
  18                 try {
  19                         solve();
  20                 } catch (Throwable t) {
  21                         t.printStackTrace();
  22                         System.exit(1);
  23                 }
  24         }
  25
  26         private BufferedReader in;
  27         private PrintWriter out;
  28
  29         private void solve() throws Exception {
  30                 in = new BufferedReader(new FileReader(FILE_NAME + ".in"));
  31                 out = new PrintWriter(new File(FILE_NAME + ".out"));
  32
  33                 StringTokenizer st = new StringTokenizer(in.readLine());
  34                 n = Integer.parseInt(st.nextToken());
  35                 m = Integer.parseInt(st.nextToken());
  36
  37                 w = new int[m][26];
  38                 words = new TreeSet<String>();
  39                 for (int i = 0; i < m; i++) {
  40                         String word = in.readLine();
  41                         words.add(word);
  42                         for (char c : word.toCharArray()) {
  43                                 w[i][c - 'A']++;
  44                         }
  45                 }
  46
  47
  48                 lim = m + n + 1;
  49
  50                 newWords = new TreeSet<NewWord>();
  51                 add("");
  52
  53                 NewWord cur = newWords.first();
  54
  55                 for (int k = 0; k < lim; k++) {
  56                         for (char c = 'A'; c <= 'Z'; c++) {
  57                                 add(cur.word + c);
  58                         }
  59                         cur = newWords.higher(cur);
  60                 }
  61
  62
  63
  64
  65
  66                 newWords.remove(newWords.first());
  67
  68                 for (NewWord nw : newWords) {
  69                         if (words.contains(nw.word)) {
  70                                 continue;
  71                         }
  72                         out.println(nw.word);
  73                         n--;
  74                         if (n == 0) {
  75                                 break;
  76                         }
  77                 }
  78
  79                 in.close();
  80                 out.close();
  81         }
  82
  83         int[] a = new int[26];
  84
  85         private void add(String s) {
  86                 Arrays.fill(a, 0);
  87                 for (int i = 0; i < s.length(); i++) {
  88                         char c = s.charAt(i);
  89                         a[c - 'A']++;
  90                 }
  91                 int cnt = 0;
  92                 LOOP: for (int[] ww : w) {
  93                         for (int i = 0; i < 26; i++) {
  94                                 if (a[i] > ww[i]) {
  95                                         continue LOOP;
  96                                 }
  97                         }
  98                         cnt++;
  99                 }
 100                 newWords.add(new NewWord(s, cnt));
 101                 if (newWords.size() > lim) {
 102                         newWords.remove(newWords.last());
 103                 }
 104         }
 105
 106         static class NewWord implements Comparable<NewWord> {
 107                 String word;
 108                 int score;
 109
 110                 NewWord(String word, int score) {
 111                         this.word = word;
 112                         this.score = score;
 113                 }
 114
 115                 public int compareTo(NewWord o) {
 116                         int res = o.score - score;
 117                         if (res == 0) {
 118                                 res = word.compareTo(o.word);
 119                         }
 120                         return res;
 121                 }
 122         }
 123
 124         public static void main(String[] args) {
 125                 new Thread(new funny_ia()).start();
 126         }
 127 }