NEERC/funny/funny_gk_wa_skip_words.java

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