NEERC/business/business_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.StringTokenizer;
   6
   7 public class business_petr implements Runnable {
   8     private void solve() throws IOException {
   9         int n = nextInt();
  10         int m = nextInt();
  11         int res = Integer.MAX_VALUE;
  12         for (int i = 0; i < m; ++i) {
  13             int u = nextInt();
  14             int d = nextInt();
  15             int l = -1;
  16             int r = n + 1;
  17             while (r > l + 1) {
  18                 int mm = (l + r) / 2;
  19                 int z = mm * u - (n - mm) * d;
  20                 if (z > 0) {
  21                     r = mm;
  22                     res = Math.min(res, z);
  23                 } else {
  24                     l = mm;
  25                 }
  26             }
  27         }
  28         writer.println(res);
  29     }
  30
  31
  32     public static void main(String[] args) throws InterruptedException {
  33         Thread thread = new Thread(new business_petr());
  34         thread.start();
  35         thread.join();
  36     }
  37
  38     static final String TASK_ID = "business";
  39     static final String IN_FILE = TASK_ID + ".in";
  40     static final String OUT_FILE = TASK_ID + ".out";
  41     BufferedReader reader;
  42     StringTokenizer tokenizer;
  43     PrintWriter writer;
  44
  45     public void run() {
  46         try {
  47             reader = new BufferedReader(new FileReader(IN_FILE));
  48             tokenizer = null;
  49             writer = new PrintWriter(OUT_FILE);
  50             solve();
  51             reader.close();
  52             writer.close();
  53         } catch (Exception e) {
  54             e.printStackTrace();
  55             System.exit(1);
  56         }
  57     }
  58
  59     int nextInt() throws IOException {
  60         return Integer.parseInt(nextToken());
  61     }
  62
  63     long nextLong() throws IOException {
  64         return Long.parseLong(nextToken());
  65     }
  66
  67     double nextDouble() throws IOException {
  68         return Double.parseDouble(nextToken());
  69     }
  70
  71     String nextToken() throws IOException {
  72         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  73             tokenizer = new StringTokenizer(reader.readLine());
  74         }
  75         return tokenizer.nextToken();
  76     }
  77 }