NEERC/business/business_re.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 /**
   5  * Solution for NEERC'2009 Problem B: Business Center
   6  * This solution checks correctness of the input.
   7  * @author Roman Elizarov
   8  */
   9 public class business_re {
  10
  11         public static void main(String[] args) throws Exception {
  12                 new business_re().go();
  13         }
  14
  15         void go() throws Exception {
  16                 read();
  17                 solve();
  18                 write();
  19         }
  20
  21         int n;
  22         int m;
  23         int[] u;
  24         int[] d;
  25
  26         void read() throws Exception {
  27                 Scanner in = new Scanner(new File("business.in"));
  28                 in.useLocale(Locale.US);
  29                 n = in.nextInt();
  30                 m = in.nextInt();
  31                 in.nextLine();
  32                 assert n >= 1 && n <= 1000000;
  33                 assert m >= 1 && m <= 2000;
  34                 u = new int[m];
  35                 d = new int[m];
  36                 for (int i = 0; i < m; i++) {
  37                     u[i] = in.nextInt();
  38                         d[i] = in.nextInt();
  39                         in.nextLine();
  40                         assert u[i] >= 1 && u[i] <= 1000;
  41                         assert d[i] >= 1 && d[i] <= 1000;
  42                 }
  43                 in.close();
  44         }
  45
  46         int lowest = Integer.MAX_VALUE;
  47
  48         void solve() {
  49                 for (int i = 0; i < m; i++) {
  50                     // min { a * u - (n - a) * d }
  51                         //       a * (u + d) = n * d
  52                         //       a = n * d / (u + d)
  53                         int a = n * d[i] / (u[i] + d[i]) + 1;
  54                         int res = a * u[i] - (n - a) * d[i];
  55                         lowest = Math.min(lowest, res);
  56                 }
  57         }
  58
  59         void write() throws Exception {
  60                 PrintWriter out = new PrintWriter("business.out");
  61                 out.println(lowest);
  62                 out.close();
  63         }
  64
  65 //----------------- just for validation ------------------
  66
  67         /**
  68          * Strict scanner to veryfy 100% correspondence between input files and input file format specification.
  69          * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
  70          * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
  71          */
  72         public class Scanner {
  73                 private final BufferedReader in;
  74                 private String line = "";
  75                 private int pos;
  76                 private int lineNo;
  77                 private boolean localeset;
  78
  79                 public Scanner(File source) throws FileNotFoundException {
  80                         in = new BufferedReader(new FileReader(source));
  81                         nextLine();
  82                 }
  83
  84                 public void close() {
  85                         assert line == null : "Extra data at the end of file";
  86                         try {
  87                                 in.close();
  88                         } catch (IOException e) {
  89                                 throw new AssertionError("Failed to close with " + e);
  90                         }
  91                 }
  92
  93                 public void nextLine() {
  94                         assert line != null : "EOF";
  95                         assert pos == line.length() : "Extra characters on line " + lineNo;
  96                         try {
  97                                 line = in.readLine();
  98                         } catch (IOException e) {
  99                                 throw new AssertionError("Failed to read line with " + e);
 100                         }
 101                         pos = 0;
 102                         lineNo++;
 103                 }
 104
 105                 public String next() {
 106                         assert line != null : "EOF";
 107                         assert line.length() > 0 : "Empty line " + lineNo;
 108                         if (pos == 0)
 109                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
 110                         else {
 111                                 assert pos < line.length() : "Line " + lineNo + " is over";
 112                                 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
 113                                 pos++;
 114                                 assert pos < line.length() : "Line " + lineNo + " is over";
 115                                 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
 116                         }
 117                         StringBuilder sb = new StringBuilder();
 118                         while (pos < line.length() && line.charAt(pos) > ' ')
 119                                 sb.append(line.charAt(pos++));
 120                         return sb.toString();
 121                 }
 122
 123                 public int nextInt() {
 124                         String s = next();
 125                         assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 126                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 127                         try {
 128                                 return Integer.parseInt(s);
 129                         } catch (NumberFormatException e) {
 130                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 131                         }
 132                 }
 133
 134                 public double nextDouble() {
 135                         assert localeset : "Locale must be set with useLocale(Locale.US)";
 136                         String s = next();
 137                         assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
 138                         assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
 139                         try {
 140                                 return Double.parseDouble(s);
 141                         } catch (NumberFormatException e) {
 142                                 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
 143                         }
 144                 }
 145
 146                 public void useLocale(Locale locale) {
 147                         assert locale == Locale.US;
 148                         localeset = true;
 149                 }
 150         }
 151 }