NEERC/funny/funny_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.HashSet;
   5 import java.util.PriorityQueue;
   6 import java.util.Scanner;
   7
   8 public class funny_mb implements Runnable {
   9     private Scanner in;
  10     private PrintWriter out;
  11     private short[][] playCounters;
  12     private PriorityQueue<Item> queue = new PriorityQueue<Item>();
  13     private HashSet<String> queued = new HashSet<String>();
  14     private HashSet<String> playWords = new HashSet<String>();
  15
  16     class Item implements Comparable<Item> {
  17         public final String word;
  18         public final short[] counters;
  19         public final int bonus;
  20
  21         public Item(String word, short[] counters, int bonus) {
  22
  23             this.word = word;
  24             this.counters = counters;
  25             this.bonus = bonus;
  26         }
  27
  28         public int compareTo(Item o) {
  29             return o.bonus - bonus;
  30         }
  31     }
  32
  33     public static void main(String[] args) {
  34         new Thread(new funny_mb()).start();
  35     }
  36
  37     public void run() {
  38         try {
  39             in = new Scanner(new FileReader("funny.in"));
  40             out = new PrintWriter("funny.out");
  41
  42             solve();
  43
  44             in.close();
  45             out.close();
  46         } catch (IOException e) {
  47             e.printStackTrace();
  48         }
  49     }
  50
  51     private short[] countLetters(String word) {
  52         short[] counters = new short[26];
  53         for (int i = 0; i < word.length(); ++i) {
  54             char ch = word.charAt(i);
  55             counters[ch - 'A']++;
  56         }
  57         return counters;
  58     }
  59
  60     private boolean isLeq(short[] lhsCounters, short[] rhsCounters) {
  61         for (int i = 0; i < 26; i++) {
  62             if (lhsCounters[i] > rhsCounters[i]) {
  63                 return false;
  64             }
  65         }
  66         return true;
  67     }
  68
  69     private int calcBonus(short[] candidateCounters) {
  70         int bonus = 0;
  71         for (short[] counters : playCounters) {
  72             if (isLeq(candidateCounters, counters)) {
  73                 bonus++;
  74             }
  75         }
  76         return bonus;
  77     }
  78
  79     private void tryEnqueue(String word, short[] counters) {
  80         if (queued.add(word)) {
  81             final int bonus = calcBonus(counters);
  82             final Item item = new Item(word, counters, bonus);
  83             queue.add(item);
  84         }
  85     }
  86
  87     private void solve() {
  88         final int n = in.nextInt();
  89         final int m = in.nextInt();
  90         in.nextLine();
  91
  92         playCounters = new short[m][];
  93         for (int i = 0; i < m; i++) {
  94             String word = in.nextLine();
  95             playWords.add(word);
  96             playCounters[i] = countLetters(word);
  97         }
  98
  99         for (int i = 0; i < 26; i++) {
 100             String word = Character.toString((char) ('A' + i));
 101             final short[] counters = countLetters(word);
 102             tryEnqueue(word, counters);
 103         }
 104
 105         int numOut = 0;
 106         while (numOut < n) {
 107             final Item item = queue.remove();
 108             if (!playWords.contains(item.word)) {
 109                 out.println(item.word);
 110                 numOut++;
 111             }
 112             for (int i = 0; i < 26; i++) {
 113                 String newWord = item.word + (char)('A' + i);
 114                 short[] newCounters = item.counters.clone();
 115                 newCounters[i]++;
 116                 tryEnqueue(newWord, newCounters);
 117             }
 118         }
 119     }
 120 }