NEERC/javacert/javacert_re.java

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