NEERC/javacert/javacert_re_backtrack.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * Solution for NEERC'2009 Problem J: Java Certification
   6  * This solution is slow (uses backtracking)
   7  * This solution checks correctness of the input.
   8  * @author Roman Elizarov
   9  */
  10 public class javacert_re_backtrack {
  11
  12         public static void main(String[] args) throws Exception {
  13                 new javacert_re_backtrack().go();
  14         }
  15
  16         void go() throws Exception {
  17                 read();
  18                 solve();
  19                 write();
  20         }
  21
  22         int k;
  23         int n;
  24         int m;
  25         int[] p;
  26
  27         void read() throws Exception {
  28                 Scanner in = new Scanner(new File("javacert.in"));
  29                 in.useLocale(Locale.US);
  30                 k = in.nextInt();
  31                 n = in.nextInt();
  32                 m = in.nextInt();
  33                 in.nextLine();
  34                 assert k >= 0 && k <= n;
  35                 assert n >= 1 && n <= 100;
  36                 assert m >= 1 && m <= 10;
  37                 p = new int[m];
  38                 for (int i = 0; i < m; i++) {
  39                     p[i] = in.nextInt();
  40                         in.nextLine();
  41                         assert p[i] >= 0 && p[i] <= 100;
  42                 }
  43                 in.close();
  44         }
  45
  46         static class Pair {
  47                 int wi;
  48                 int ni;
  49
  50                 Pair(int wi, int ni) {
  51                         this.wi = wi;
  52                         this.ni = ni;
  53                 }
  54
  55                 @Override
  56                 public String toString() {
  57                         return wi + " " + ni + " " + (100.0*(ni - wi) / ni);
  58                 }
  59         }
  60
  61         int w;
  62         List<List<Pair>> llp;
  63         Pair[] cursol;
  64         Pair[] sol;
  65         int soldiff;
  66
  67         void solve() {
  68                 buildPairs();
  69                 sortPairs();
  70                 w = n - k;
  71                 cursol = new Pair[m];
  72                 soldiff = Integer.MAX_VALUE;
  73                 find(0, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
  74         }
  75
  76         private void buildPairs() {
  77                 llp = new ArrayList<List<Pair>>();
  78                 for (int i = 0; i < m; i++) {
  79                         llp.add(new ArrayList<Pair>());
  80                 }
  81                 for (int ni = 1; ni <= n; ni++) {
  82                         for (int wi = 0; wi <= ni; wi++) {
  83                                 int ppp = 100 * (ni - wi);
  84                                 int pp = (2 * ppp + ni) / (2 * ni);
  85                                 if (2 * ppp % ni == 0 && 2 * ppp / ni % 2 == 1 && pp % 2 == 1)
  86                                         pp--;
  87                                 for (int i = 0; i < m; i++) {
  88                                     if (p[i] == pp)
  89                                             llp.get(i).add(new Pair(wi, ni));
  90                                 }
  91                         }
  92                 }
  93         }
  94
  95         private void sortPairs() {
  96                 final double mid = n / m;
  97                 for (int i = 0; i < m; i++) {
  98                     Collections.sort(llp.get(i), new Comparator<Pair>() {
  99                             public int compare(Pair p1, Pair p2) {
 100                                     double d1 = Math.abs(p1.ni - mid);
 101                                     double d2 = Math.abs(p2.ni - mid);
 102                                     return Double.compare(d1, d2);
 103                             }
 104                     });
 105                 }
 106         }
 107
 108         void find(int i, int ws, int ns, int minni, int maxni) {
 109                 if (ns > n || ws > w)
 110                         return;
 111                 int diff = maxni - minni;
 112                 if (diff >= soldiff)
 113                         return;
 114                 if (i == m) {
 115                         if (ns < n || ws < w)
 116                                 return;
 117                         soldiff = diff;
 118                         sol = cursol.clone();
 119                         return;
 120                 }
 121                 for (Pair p : llp.get(i)) {
 122                         cursol[i] = p;
 123                         find(i + 1, ws + p.wi, ns + p.ni, Math.min(minni, p.ni), Math.max(maxni, p.ni));
 124                 }
 125         }
 126
 127         void write() throws Exception {
 128                 PrintWriter out = new PrintWriter("javacert.out");
 129                 for (int i = 0; i < m; i++) {
 130                     out.printf("%d %d%n", sol[i].wi,  sol[i].ni);
 131                 }
 132                 out.close();
 133         }
 134
 135 //----------------- just for validation ------------------
 136
 137         /**
 138          * Strict scanner to veryfy 100% correspondence between input files and input file format specification.
 139          * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
 140          * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
 141          */
 142         public class Scanner {
 143                 private final BufferedReader in;
 144                 private String line = "";
 145                 private int pos;
 146                 private int lineNo;
 147                 private boolean localeset;
 148
 149                 public Scanner(File source) throws FileNotFoundException {
 150                         in = new BufferedReader(new FileReader(source));
 151                         nextLine();
 152                 }
 153
 154                 public void close() {
 155                         assert line == null : "Extra data at the end of file";
 156                         try {
 157                                 in.close();
 158                         } catch (IOException e) {
 159                                 throw new AssertionError("Failed to close with " + e);
 160                         }
 161                 }
 162
 163                 public void nextLine() {
 164                         assert line != null : "EOF";
 165                         assert pos == line.length() : "Extra characters on line " + lineNo;
 166                         try {
 167                                 line = in.readLine();
 168                         } catch (IOException e) {
 169                                 throw new AssertionError("Failed to read line with " + e);
 170                         }
 171                         pos = 0;
 172                         lineNo++;
 173                 }
 174
 175                 public String next() {
 176                         assert line != null : "EOF";
 177                         assert line.length() > 0 : "Empty line " + lineNo;
 178                         if (pos == 0)
 179                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
 180                         else {
 181                                 assert pos < line.length() : "Line " + lineNo + " is over";
 182                                 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
 183                                 pos++;
 184                                 assert pos < line.length() : "Line " + lineNo + " is over";
 185                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
 186                         }
 187                         StringBuilder sb = new StringBuilder();
 188                         while (pos < line.length() && line.charAt(pos) > ' ')
 189                                 sb.append(line.charAt(pos++));
 190                         return sb.toString();
 191                 }
 192
 193                 public int nextInt() {
 194                         String s = next();
 195                         assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 196                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 197                         try {
 198                                 return Integer.parseInt(s);
 199                         } catch (NumberFormatException e) {
 200                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 201                         }
 202                 }
 203
 204                 public double nextDouble() {
 205                         assert localeset : "Locale must be set with useLocale(Locale.US)";
 206                         String s = next();
 207                         assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 208                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 209                         try {
 210                                 return Double.parseDouble(s);
 211                         } catch (NumberFormatException e) {
 212                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 213                         }
 214                 }
 215
 216                 public void useLocale(Locale locale) {
 217                         assert locale == Locale.US;
 218                         localeset = true;
 219                 }
 220         }
 221 }