NEERC/javacert/javacert_pm.java

   1 import java.util.Scanner;
   2 import java.io.File;
   3 import java.io.FileNotFoundException;
   4 import java.io.PrintWriter;
   5
   6 public class javacert_pm {
   7
   8     public static void main(String[] args) throws FileNotFoundException {
   9         Scanner in = new Scanner(new File("javacert.in"));
  10         PrintWriter out = new PrintWriter("javacert.out");
  11
  12         int k = in.nextInt();
  13         int n = in.nextInt();
  14         int m = in.nextInt();
  15         int[] p = new int[m];
  16         for (int i = 0; i < m; i++) {
  17             p[i] = in.nextInt();
  18         }
  19
  20         int res = 1000;
  21         int[] rn = new int[m];
  22         int[] rw = new int[m];
  23
  24         for (int low = 1; low <= n / m; low++) {
  25             int[][][] a = new int[m + 1][n + 1][n + 1];
  26             int[][][] pn = new int[m + 1][n + 1][n + 1];
  27             int[][][] pw = new int[m + 1][n + 1][n + 1];
  28             a[0][0][0] = low;
  29             for (int i = 0; i < m; i++) {
  30                 for (int n2 = low; n2 <= n; n2++) {
  31                     int w2 = (int) Math.round((100 - p[i]) * n2 * 0.01);
  32                     int pp = (int) Math.rint(100.0 * (n2 - w2) / n2);
  33                     if (pp == p[i]) {
  34                         for (int n1 = 0; n1 + n2 <= n; n1++) {
  35                             for (int w1 = 0; w1 <= n; w1++) {
  36                                 if (a[i][n1][w1] > 0) {
  37                                     int r = Math.max(a[i][n1][w1], n2);
  38                                     if (a[i + 1][n1 + n2][w1 + w2] == 0 ||
  39                                             a[i + 1][n1 + n2][w1 + w2] > r) {
  40                                         a[i + 1][n1 + n2][w1 + w2] = r;
  41                                         pn[i + 1][n1 + n2][w1 + w2] = n2;
  42                                         pw[i + 1][n1 + n2][w1 + w2] = w2;
  43                                     }
  44                                 }
  45                             }
  46                         }
  47                     }
  48                 }
  49             }
  50             if (a[m][n][n - k] > 0) {
  51                 if (a[m][n][n - k] - low < res) {
  52                     res = a[m][n][n - k] - low;
  53                     int nn = n;
  54                     int ww = n - k;
  55                     for (int i = m; i > 0; i--) {
  56                         int qn = pn[i][nn][ww];
  57                         int qw = pw[i][nn][ww];
  58                         rn[i - 1] = qn;
  59                         rw[i - 1] = qw;
  60                         nn -= qn;
  61                         ww -= qw;
  62                     }
  63                 }
  64             }
  65         }
  66         for (int i = 0; i < m; i++) {
  67             out.println(rw[i] + " " + rn[i]);
  68         }
  69         in.close();
  70         out.close();
  71     }
  72 }