NEERC/funny/funny_gk.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 public class funny_gk {
   5     static Scanner in;
   6     static PrintWriter out;
   7
   8     static int MAX_N = 100;
   9     static int MAX_M = 1000;
  10
  11     static final int MAX_W = 100;
  12     static final int MIN_CH = 'A';
  13     static final int MAX_CH = 'Z';
  14
  15     List<int[]> letterss;
  16
  17     static class Entry implements Comparable<Entry> {
  18         final String word;
  19         final List<Integer> in;
  20
  21         Entry(String word, List<Integer> in) {
  22                 this.word = word;
  23                 this.in = in;
  24         }
  25
  26                 @Override
  27                 public int compareTo(Entry that) {
  28                         return that.in.size() - this.in.size();
  29                 }
  30     }
  31
  32     Queue<Entry> queue = new PriorityQueue<Entry>();
  33     Set<String> queued = new HashSet<String>();
  34
  35         private void enqueue(String word, List<Integer> in) {
  36                 if (queued.add(word)) {
  37                         in = count(word, in);
  38                         if (!in.isEmpty()) {
  39                                 queue.add(new Entry(word, in));
  40                         }
  41                 }
  42         }
  43
  44         private List<Integer> count(String word, List<Integer> in) {
  45                 int[] letters = letters(word);
  46                 List<Integer> result = new ArrayList<Integer>();
  47                 for (Integer i : in) {
  48                         if (match(letters, letterss.get(i))) {
  49                                 result.add(i);
  50                         }
  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         Set<String> solve(int n, Set<String> words) {
  74                 letterss = new ArrayList<int[]>();
  75         for (String word : words) {
  76                 letterss.add(letters(word));
  77         }
  78
  79         List<Integer> all = new ArrayList<Integer>();
  80         for (int i = 0; i < words.size(); i++) {
  81                 all.add(i);
  82         }
  83         enqueue("", all);
  84
  85         Set<String> result = new TreeSet<String>();
  86         int processed = 0;
  87         while (!queue.isEmpty() && result.size() < n) {
  88                 Entry entry = queue.remove();
  89                         String word = entry.word;
  90                 if (word.length() > 0 && !words.contains(word)) {
  91                         result.add(word);
  92                 }
  93                 processed++;
  94
  95                 for (int i = 0; i < 26; i++) {
  96                         enqueue(word + (char) ('A' + i), entry.in);
  97                 }
  98         }
  99
 100         StringBuilder sb = new StringBuilder();
 101         for (int i = 0; result.size() < n; i++) {
 102                 sb.append('A');
 103                 String word = sb.toString();
 104                 if (!words.contains(word)) {
 105                         result.add(word);
 106                 }
 107         }
 108                 return result;
 109         }
 110
 111         public void run() throws IOException {
 112         int n = in.nextInt();
 113         int m = in.nextInt();
 114
 115         assert 1 <= n && n <= MAX_N;
 116         assert 1 <= m && m <= MAX_M;
 117
 118         Set<String> words = new HashSet<String>();
 119         for (int i = 0; i < m; i++) {
 120                 String word = in.next();
 121             words.add(word);
 122
 123             assert 1 <= word.length() && word.length() <= MAX_W;
 124             for (char ch : word.toCharArray()) {
 125                 assert MIN_CH <= ch && ch <= MAX_CH;
 126             }
 127         }
 128         assert !in.hasNext();
 129
 130         Set<String> result = solve(n, words);
 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().run();
 142
 143         in.close();
 144         out.close();
 145     }
 146 }