NEERC/funny/funny_gk_wa_no_generated.java

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