NEERC/funny/funny_gk_wa_short.java

   1 /* Generates all short words and chooses best */
   2
   3 import java.io.File;
   4 import java.io.IOException;
   5 import java.io.PrintWriter;
   6 import java.util.ArrayList;
   7 import java.util.Collections;
   8 import java.util.HashSet;
   9 import java.util.List;
  10 import java.util.Scanner;
  11 import java.util.Set;
  12 import java.util.TreeSet;
  13
  14 public class funny_gk_wa_short {
  15     static Scanner in;
  16     static PrintWriter out;
  17
  18     static int MAX_N = 100;
  19     static int MAX_M = 1000;
  20
  21     static final int MAX_W = 100;
  22     static final int MIN_CH = 'A';
  23     static final int MAX_CH = 'Z';
  24
  25     List<int[]> letterss;
  26
  27     static class Entry implements Comparable<Entry> {
  28         int count;
  29         String word;
  30
  31         Entry(int count, String word) {
  32                 this.count = count;
  33                 this.word = word;
  34         }
  35
  36                 @Override
  37                 public int compareTo(Entry that) {
  38                         return that.count - this.count;
  39                 }
  40     }
  41
  42         private int count(String word) {
  43                 int[] letters = letters(word);
  44                 int result = 0;
  45                 for (int[] wordLetters : letterss) {
  46                         if (match(letters, wordLetters)) {
  47                                 result++;
  48                         }
  49                 }
  50                 return result;
  51         }
  52
  53         private boolean match(int[] letters, int[] wordLetters) {
  54                 for (int i = 0; i < 26; i++) {
  55                         if (letters[i] > wordLetters[i]) {
  56                                 return false;
  57                         }
  58                 }
  59                 return true;
  60         }
  61
  62         private int[] letters(String word) {
  63                 int[] letters = new int[26];
  64                 for (char ch : word.toCharArray()) {
  65                         letters[ch - MIN_CH]++;
  66                 }
  67                 return letters;
  68         }
  69
  70
  71         public void run() throws IOException {
  72         int n = in.nextInt();
  73         int m = in.nextInt();
  74
  75         assert 1 <= n && n <= MAX_N;
  76         assert 1 <= m && m <= MAX_M;
  77
  78         Set<String> words = new HashSet<String>();
  79         for (int i = 0; i < m; i++) {
  80                 String word = in.next();
  81             words.add(word);
  82
  83             assert 1 <= word.length() && word.length() <= MAX_W;
  84             for (char ch : word.toCharArray()) {
  85                 assert MIN_CH <= ch && ch <= MAX_CH;
  86             }
  87         }
  88
  89         Set<Character> letters = new HashSet<Character>();
  90         assert !in.hasNext();
  91                 letterss = new ArrayList<int[]>();
  92                 for (String word : words) {
  93                         letterss.add(letters(word));
  94                         for (char ch : word.toCharArray()) {
  95                                 letters.add(ch);
  96                         }
  97                 }
  98
  99                 int maxWords = 2000000 / words.size();
 100                 List<Entry> queue = new ArrayList<Entry>();
 101                 queue.add(new Entry(0, ""));
 102                 int head = 0;
 103                 while (head < queue.size() && queue.size() < maxWords) {
 104                         String word = queue.get(head++).word;
 105                         for (int i = 0; i < 26; i++) {
 106                                 String nword = word + (char) ('A' + i);
 107                                 int count = count(nword);
 108                                 if (count != 0) {
 109                                         queue.add(new Entry(count, nword));
 110                                 }
 111                         }
 112                 }
 113                 Collections.sort(queue);
 114                 head = 0;
 115                 Set<String> result = new TreeSet<String>();
 116                 while (head < queue.size() && result.size() < n) {
 117                         String word = queue.get(head++).word;
 118                         if (word.length() > 0 && !words.contains(word)) {
 119                                 result.add(word);
 120                         }
 121                 }
 122
 123         StringBuilder sb = new StringBuilder();
 124         for (int i = 0; result.size() < n; i++) {
 125                 sb.append('A');
 126                 String word = sb.toString();
 127                 if (!words.contains(word)) {
 128                         result.add(word);
 129                 }
 130         }
 131
 132         for (String word : result) {
 133                 out.println(word);
 134         }
 135     }
 136
 137     public static void main(String[] args) throws Exception {
 138         in = new Scanner(new File("funny.in"));
 139         out = new PrintWriter("funny.out");
 140
 141         new funny_gk_wa_short().run();
 142
 143         in.close();
 144         out.close();
 145     }
 146 }