NEERC/funny/funny_petr.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.*;
   6
   7 public class funny_petr implements Runnable {
   8     static int[][] wcnt;
   9
  10     static class State implements Comparable<State> {
  11         int[] cnt = new int[26];
  12         int score;
  13
  14         State(int[] cnt) {
  15             this.cnt = cnt;
  16             score = getScore();
  17         }
  18
  19         @Override
  20         public boolean equals(Object o) {
  21             if (this == o) return true;
  22             if (o == null || getClass() != o.getClass()) return false;
  23
  24             State state = (State) o;
  25
  26             if (!Arrays.equals(cnt, state.cnt)) return false;
  27
  28             return true;
  29         }
  30
  31         @Override
  32         public int hashCode() {
  33             int result = cnt != null ? Arrays.hashCode(cnt) : 0;
  34             return result;
  35         }
  36
  37         public int compareTo(State state) {
  38             int z = -score + state.score;
  39             if (z != 0)
  40                 return z;
  41             for (int i = 0; i < 26; ++i)
  42                 if (cnt[i] != state.cnt[i])
  43                     return cnt[i] - state.cnt[i];
  44             return 0;
  45         }
  46
  47         public int getScore() {
  48             score = 0;
  49             for (int i = 0; i < wcnt.length; ++i) {
  50                 boolean ok = true;
  51                 for (int j = 0; j < 26; ++j)
  52                     if (cnt[j] > wcnt[i][j]) {
  53                         ok = false;
  54                         break;
  55                     }
  56                 if (ok)
  57                     ++score;
  58             }
  59             return score;
  60         }
  61     }
  62
  63     int n;
  64
  65     private void solve() throws IOException {
  66         int n = nextInt();
  67         int m = nextInt();
  68         this.n = n;
  69         String[] w = new String[m];
  70         for (int i = 0; i < m; ++i) {
  71             w[i] = nextToken();
  72         }
  73         wcnt = new int[m][26];
  74         for (int i = 0; i < m; ++i)
  75             for (int j = 0; j < w[i].length(); ++j)
  76                 ++wcnt[i][w[i].charAt(j) - 'A'];
  77         TreeSet<State> queue = new TreeSet<State>();
  78         queue.add(new State(new int[26]));
  79         Set<String> got = new HashSet<String>();
  80         got.add("");
  81         got.addAll(Arrays.asList(w));
  82         List<String> sols = new ArrayList<String>();
  83         while (sols.size() < n) {
  84             State cur = queue.first();
  85             queue.remove(cur);
  86             addSols(got, sols, cur);
  87             if (sols.size() >= n)
  88                 break;
  89             for (int i = 0; i < 26; ++i) {
  90                 int[] z = cur.cnt.clone();
  91                 ++z[i];
  92                 State s = new State(z);
  93                 queue.add(s);
  94             }
  95         }
  96         for (String s : sols)
  97             writer.println(s);
  98     }
  99
 100     private void addSols(Set<String> got, List<String> sols, State cur) {
 101         rec(got, sols, cur.cnt.clone(), "");
 102     }
 103
 104     private boolean rec(Set<String> got, List<String> sols, int[] cnt, String prefix) {
 105         boolean any = false;
 106         for (int i = 0; i < 26; ++i)
 107             if (cnt[i] > 0) {
 108                 --cnt[i];
 109                 if (rec(got, sols, cnt, prefix + (char) ('A' + i)))
 110                     return true;
 111                 ++cnt[i];
 112                 any = true;
 113             }
 114         if (!any) {
 115             if (!got.contains(prefix)) {
 116                 sols.add(prefix);
 117                 if (sols.size() >= n)
 118                     return true;
 119             }
 120         }
 121         return false;
 122     }
 123
 124
 125     public static void main(String[] args) throws InterruptedException {
 126         Thread thread = new Thread(new funny_petr());
 127         thread.start();
 128         thread.join();
 129     }
 130
 131     static final String TASK_ID = "funny";
 132     static final String IN_FILE = TASK_ID + ".in";
 133     static final String OUT_FILE = TASK_ID + ".out";
 134     BufferedReader reader;
 135     StringTokenizer tokenizer;
 136     PrintWriter writer;
 137
 138     public void run() {
 139         try {
 140             reader = new BufferedReader(new FileReader(IN_FILE));
 141             tokenizer = null;
 142             writer = new PrintWriter(OUT_FILE);
 143             solve();
 144             reader.close();
 145             writer.close();
 146         } catch (Exception e) {
 147             e.printStackTrace();
 148             System.exit(1);
 149         }
 150     }
 151
 152     int nextInt() throws IOException {
 153         return Integer.parseInt(nextToken());
 154     }
 155
 156     long nextLong() throws IOException {
 157         return Long.parseLong(nextToken());
 158     }
 159
 160     double nextDouble() throws IOException {
 161         return Double.parseDouble(nextToken());
 162     }
 163
 164     String nextToken() throws IOException {
 165         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
 166             tokenizer = new StringTokenizer(reader.readLine());
 167         }
 168         return tokenizer.nextToken();
 169     }
 170 }