NEERC/funny/funny_ia_wrong.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * @author Iskander Akishev
   6  */
   7 public class funny_ia_wrong implements Runnable {
   8
   9         private static final String FILE_NAME = "funny";
  10
  11         public void run() {
  12                 try {
  13                         solve();
  14                 } catch (Throwable t) {
  15                         t.printStackTrace();
  16                         System.exit(1);
  17                 }
  18         }
  19
  20         private BufferedReader in;
  21         private PrintWriter out;
  22
  23         private void solve() throws Exception {
  24                 in = new BufferedReader(new FileReader(FILE_NAME + ".in"));
  25                 out = new PrintWriter(new File(FILE_NAME + ".out"));
  26
  27                 StringTokenizer st = new StringTokenizer(in.readLine());
  28                 int n = Integer.parseInt(st.nextToken());
  29                 int m = Integer.parseInt(st.nextToken());
  30
  31                 int[][] w = new int[m][26];
  32                 TreeSet<String> words = new TreeSet<String>();
  33                 for (int i = 0; i < m; i++) {
  34                         String word = in.readLine();
  35                         words.add(word);
  36                         for (char c : word.toCharArray()) {
  37                                 w[i][c - 'A']++;
  38                         }
  39                 }
  40
  41                 //todo
  42                 Random rnd = new Random();
  43                 for (int i = 0; i < 1000; i++) {
  44                         String str = "";
  45                         for (int z = 0; z < 100; z++)
  46                                 str += (rnd.nextInt(26) + 'A');
  47                         words.add(str);
  48                 }
  49
  50                 TreeSet<NewWord> newWords = new TreeSet<NewWord>();
  51
  52                 for (char c1 = 'A'; c1 <= 'Z'; c1++) {
  53                         int cnt = 0;
  54                         for (int[] ww : w) {
  55                                 ww[c1 - 'A']--;
  56                                 if (ww[c1 - 'A'] >= 0)
  57                                         cnt++;
  58                                 ww[c1 - 'A']++;
  59                         }
  60                         String str = String.valueOf(new char[] {c1});
  61                         if (!words.contains(str)) {
  62                                 newWords.add(new NewWord(str, cnt));
  63                                 if (newWords.size() > n)
  64                                         newWords.remove(newWords.last());
  65                         }
  66                 }
  67                 for (char c1 = 'A'; c1 <= 'Z'; c1++) {
  68                         for (char c2 = 'A'; c2 <= 'Z'; c2++) {
  69                                 int cnt = 0;
  70                                 for (int[] ww : w) {
  71                                         ww[c1 - 'A']--;
  72                                         ww[c2 - 'A']--;
  73                                         if ((ww[c1 - 'A'] >= 0) && (ww[c2 - 'A'] >= 0))
  74                                                 cnt++;
  75                                         ww[c1 - 'A']++;
  76                                         ww[c2 - 'A']++;
  77                                 }
  78                                 String str = String.valueOf(new char[] {c1, c2});
  79                                 if (!words.contains(str)) {
  80                                         newWords.add(new NewWord(str, cnt));
  81                                         if (newWords.size() > n)
  82                                                 newWords.remove(newWords.last());
  83                                 }
  84                         }
  85                 }
  86                 for (char c1 = 'A'; c1 <= 'Z'; c1++) {
  87                         for (char c2 = 'A'; c2 <= 'Z'; c2++) {
  88                                 for (char c3 = 'A'; c3 <= 'Z'; c3++) {
  89                                         int cnt = 0;
  90                                         for (int[] ww : w) {
  91                                                 ww[c1 - 'A']--;
  92                                                 ww[c2 - 'A']--;
  93                                                 ww[c3 - 'A']--;
  94                                                 if ((ww[c1 - 'A'] >= 0) && (ww[c2 - 'A'] >= 0) && (ww[c3 - 'A'] >= 0))
  95                                                         cnt++;
  96                                                 ww[c1 - 'A']++;
  97                                                 ww[c2 - 'A']++;
  98                                                 ww[c3 - 'A']++;
  99                                         }
 100                                         String str = String.valueOf(new char[] {c1, c2, c3});
 101                                         if (!words.contains(str)) {
 102                                                 newWords.add(new NewWord(str, cnt));
 103                                                 if (newWords.size() > n)
 104                                                         newWords.remove(newWords.last());
 105                                         }
 106                                 }
 107                         }
 108                 }
 109                 for (char c1 = 'A'; c1 <= 'Z'; c1++) {
 110                         for (char c2 = 'A'; c2 <= 'Z'; c2++) {
 111                                 for (char c3 = 'A'; c3 <= 'Z'; c3++) {
 112                                         for (char c4 = 'A'; c4 <= 'Z'; c4++) {
 113                                                 int cnt = 0;
 114                                                 for (int[] ww : w) {
 115                                                         ww[c1 - 'A']--;
 116                                                         ww[c2 - 'A']--;
 117                                                         ww[c3 - 'A']--;
 118                                                         ww[c4 - 'A']--;
 119                                                         if ((ww[c1 - 'A'] >= 0) && (ww[c2 - 'A'] >= 0) && (ww[c3 - 'A'] >= 0) && (ww[c4 - 'A'] >= 0))
 120                                                                 cnt++;
 121                                                         ww[c1 - 'A']++;
 122                                                         ww[c2 - 'A']++;
 123                                                         ww[c3 - 'A']++;
 124                                                         ww[c4 - 'A']++;
 125                                                 }
 126                                                 String str = String.valueOf(new char[] {c1, c2, c3, c4});
 127                                                 if (!words.contains(str)) {
 128                                                         newWords.add(new NewWord(str, cnt));
 129                                                         if (newWords.size() > n)
 130                                                                 newWords.remove(newWords.last());
 131                                                 }
 132                                         }
 133                                 }
 134                         }
 135                 }
 136 //              for (char c1 = 'A'; c1 <= 'Z'; c1++) {
 137 //                      for (char c2 = 'A'; c2 <= 'Z'; c2++) {
 138 //                              for (char c3 = 'A'; c3 <= 'Z'; c3++) {
 139 //                                      for (char c4 = 'A'; c4 <= 'Z'; c4++) {
 140 //                                              for (char c5 = 'A'; c5 <= 'Z'; c5++) {
 141 //                                                      int cnt = 0;
 142 //                                                      for (int[] ww : w) {
 143 //                                                              ww[c1 - 'A']--;
 144 //                                                              ww[c2 - 'A']--;
 145 //                                                              ww[c3 - 'A']--;
 146 //                                                              ww[c4 - 'A']--;
 147 //                                                              ww[c5 - 'A']--;
 148 //                                                              if ((ww[c1 - 'A'] >= 0) && (ww[c2 - 'A'] >= 0) && (ww[c3 - 'A'] >= 0) && (ww[c4 - 'A'] >= 0) && (ww[c5 - 'A'] >= 0))
 149 //                                                                      cnt++;
 150 //                                                              ww[c1 - 'A']++;
 151 //                                                              ww[c2 - 'A']++;
 152 //                                                              ww[c3 - 'A']++;
 153 //                                                              ww[c4 - 'A']++;
 154 //                                                              ww[c5 - 'A']++;
 155 //                                                      }
 156 //                                                      String str = "" + c1 + c2 + c3 + c4 + c5;
 157 //                                                      if (!words.contains(str)) {
 158 //                                                              newWords.add(new NewWord(str, cnt));
 159 //                                                              if (newWords.size() > n)
 160 //                                                                      newWords.remove(newWords.last());
 161 //                                                      }
 162 //                                              }
 163 //                                      }
 164 //                              }
 165 //                      }
 166 //              }
 167
 168                 for (NewWord nw : newWords) {
 169                         out.println(nw.word);
 170                         n--;
 171                         if (n == 0) {
 172                                 break;
 173                         }
 174                 }
 175
 176                 in.close();
 177                 out.close();
 178         }
 179
 180         static class NewWord implements Comparable<NewWord> {
 181                 String word;
 182                 int score;
 183
 184                 NewWord(String word, int score) {
 185                         this.word = word;
 186                         this.score = score;
 187                 }
 188
 189                 public int compareTo(NewWord o) {
 190                         int res = o.score - score;
 191                         if (res == 0) {
 192                                 res = word.compareTo(o.word);
 193                         }
 194                         return res;
 195                 }
 196         }
 197
 198         public static void main(String[] args) {
 199                 new Thread(new funny_ia_wrong()).start();
 200         }
 201 }