NEERC/javacert/javacert_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class javacert_rs implements Runnable {
   5         private static final int inf = Integer.MAX_VALUE / 3;
   6         private BufferedReader in;
   7         private PrintWriter out;
   8
   9         private void check(boolean expr, String msg) {
  10                 if (!expr) {
  11                         throw new Error(msg);
  12                 }
  13         }
  14
  15         private void checkBounds(int n, int low, int hi, String nStr) {
  16                 check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  17         }
  18
  19         private int n, m, k;
  20         private int[][] kValue;
  21         private int[][][] w, prev;
  22
  23         private int round(int a, int b) {
  24                 if (a % b == 0) {
  25                         return a / b;
  26                 }
  27                 if ((2 * a) % b == 0) {
  28                         int r = a / b;
  29                         if (r % 2 == 1) {
  30                                 r++;
  31                         }
  32                         return r;
  33                 }
  34                 return (int) Math.round(1.0 * a / b);
  35         }
  36
  37         private void solve() throws IOException {
  38                 StringTokenizer st = new StringTokenizer(in.readLine());
  39                 k = Integer.parseInt(st.nextToken());
  40                 n = Integer.parseInt(st.nextToken());
  41                 m = Integer.parseInt(st.nextToken());
  42                 checkBounds(k, 0, n, "k");
  43                 checkBounds(n, 1, 100, "n");
  44                 checkBounds(m, 1, 10, "m");
  45
  46                 int[] p = new int[m];
  47                 for (int i = 0; i < m; i++) {
  48                         p[i] = Integer.parseInt(in.readLine());
  49                         checkBounds(p[i], 0, 100, "p[i]");
  50                 }
  51
  52                 kValue = new int[m][n + 1];
  53                 for (int i = 1; i <= n; i++) {
  54                         for (int j = 0; j < m; j++) {
  55                                 kValue[j][i] = -1;
  56                                 for (int t = 0; t <= i; t++) {
  57                                         if (round(100 * t, i) == p[j]) {
  58                                                 kValue[j][i] = t;
  59                                                 break;
  60                                         }
  61                                 }
  62                         }
  63                 }
  64
  65                 w = new int[m + 1][n + 1][k + 1];
  66                 prev = new int[m + 1][n + 1][k + 1];
  67                 int answer = inf;
  68                 int[] ansN = new int[m];
  69                 int[] ansK = new int[m];
  70                 for (int min = 1; min <= n / m; min++) {
  71                         for (int step = 0; step <= m; step++) {
  72                                 for (int u = 0; u <= n; u++) {
  73                                         for (int v = 0; v <= k; v++) {
  74                                                 w[step][u][v] = inf;
  75                                         }
  76                                 }
  77                         }
  78                         w[0][0][0] = min;
  79                         for (int step = 0; step < m; step++) {
  80                                 for (int u = 0; u <= n; u++) {
  81                                         for (int v = 0; v <= k; v++) {
  82                                                 if (w[step][u][v] == inf) {
  83                                                         continue;
  84                                                 }
  85                                                 for (int t = min; u + t <= n; t++) {
  86                                                         int tk = kValue[step][t];
  87                                                         if (tk == -1 || v + tk > k) {
  88                                                                 continue;
  89                                                         }
  90                                                         if (Math.max(w[step][u][v], t) < w[step + 1][u + t][v + tk]) {
  91                                                                 w[step + 1][u + t][v + tk] = Math.max(w[step][u][v], t);
  92                                                                 prev[step + 1][u + t][v + tk] = t;
  93                                                         }
  94                                                 }
  95                                         }
  96                                 }
  97                         }
  98                         int max = w[m][n][k];
  99                         if (max - min < answer) {
 100                                 answer = max - min;
 101                                 int u = n;
 102                                 int v = k;
 103                                 for (int step = m; step > 0; step--) {
 104                                         int t = prev[step][u][v];
 105                                         ansN[step - 1] = t;
 106                                         ansK[step - 1] = kValue[step - 1][t];
 107                                         u -= t;
 108                                         v -= kValue[step - 1][t];
 109                                 }
 110                         }
 111                 }
 112                 for (int i = 0; i < m; i++) {
 113                         out.println((ansN[i] - ansK[i]) + " " + ansN[i]);
 114                 }
 115         }
 116
 117         public static void main(String[] args) {
 118                 new Thread(new javacert_rs()).start();
 119         }
 120
 121         public void run() {
 122                 String problem = getClass().getName().split("_")[0];
 123                 try {
 124                         in = new BufferedReader(new FileReader(new File(problem + ".in")));
 125                         out = new PrintWriter(new File(problem + ".out"));
 126                         solve();
 127                         in.close();
 128                         out.close();
 129                 } catch (IOException e) {
 130                         e.printStackTrace();
 131                         System.exit(1);
 132                 }
 133         }
 134 }