NEERC/javacert/javacert_vd.java

   1 import java.io.*;
   2 import java.util.Arrays;
   3 import java.util.Scanner;
   4
   5 /**
   6  * @author Vladimir Danilov
   7  */
   8 public class javacert_vd implements Runnable {
   9
  10         private static final String FILE_NAME = "javacert";
  11         private static final int MAX_VALUE = Integer.MAX_VALUE / 2;
  12
  13         public void run() {
  14                 try {
  15                         solve();
  16                 } catch (Throwable t) {
  17                         t.printStackTrace();
  18                         System.exit(1);
  19                 }
  20         }
  21
  22         private Scanner in;
  23         private PrintWriter out;
  24
  25         private void solve() throws Exception {
  26                 in = new Scanner(new FileReader(FILE_NAME + ".in"));
  27                 out = new PrintWriter(new File(FILE_NAME + ".out"));
  28
  29                 int[][] rev = new int[101][101];
  30
  31                 for (int i = 0; i <= 100; i++) {
  32                         for (int j = 0; j <= 100; j++) {
  33                                 rev[i][j] = errorCount(i, j);
  34                         }
  35                 }
  36
  37                 int k = in.nextInt();
  38                 int n = in.nextInt();
  39                 int m = in.nextInt();
  40
  41                 int [] perc = new int[n];
  42                 for (int i = 0; i < m; i++) {
  43                         perc[i] = in.nextInt();
  44                 }
  45
  46                 int err = n - k;
  47
  48                 int result = MAX_VALUE;
  49
  50                 int [] resCount = new int[m];
  51                 int [] resErrors = new int[m];
  52
  53                 for (int min = 1; min <= n / m; min++) {
  54                         int[][][] d = new int[m + 1][n + 1][n + 1];
  55                         for (int[][] r : d) {
  56                                 for (int[] c : r) {
  57                                         Arrays.fill(c, MAX_VALUE);
  58                                 }
  59                         }
  60
  61                         int [][][] candCount = new int[m + 1][n + 1][n + 1];
  62                         int [][][] candErrors = new int[m + 1][n + 1][n + 1];
  63
  64                         d[0][0][0] = 0;
  65
  66                         for (int i = 0; i < m; i++) {
  67                                 for (int processed = min * i; processed <= n; processed++) {
  68                                         for (int errors = 0; errors <= processed; errors++) {
  69                                                 if (d[i][processed][errors] == MAX_VALUE) {
  70                                                         continue;
  71                                                 }
  72                                                 int max = n - processed;
  73                                                 for (int count = min; count <= max; count++) {
  74                                                         int newCount = processed + count;
  75                                                         int add = rev[perc[i]][count];
  76                                                         if (add != -1) {
  77                                                                 int newErrors = errors + add;
  78                                                                 int cand = Math.max(d[i][processed][errors], count);
  79                                                                 if (cand < d[i + 1][newCount][newErrors]) {
  80                                                                         d[i + 1][newCount][newErrors] = cand;
  81                                                                         candCount[i + 1][newCount][newErrors] = count;
  82                                                                         candErrors[i + 1][newCount][newErrors] = add;
  83                                                                 }
  84                                                         }
  85                                                 }
  86                                         }
  87                                 }
  88                         }
  89
  90                         if (d[m][n][err] != MAX_VALUE && result > d[m][n][err] - min) {
  91                                 int curCount = n;
  92                                 int curErrors = err;
  93                                 for (int i = m; i > 0; i--) {
  94                                         resCount[i - 1] = candCount[i][curCount][curErrors];
  95                                         resErrors[i - 1] = candErrors[i][curCount][curErrors];
  96
  97                                         curCount -= resCount[i - 1];
  98                                         curErrors -= resErrors[i - 1];
  99                                 }
 100
 101                                 result = d[m][n][err] - min;
 102                         }
 103                 }
 104
 105                 for (int i = 0; i < m; i++) {
 106                         out.printf("%d %d\n", resErrors[i], resCount[i]);
 107                 }
 108
 109                 in.close();
 110                 out.close();
 111         }
 112
 113         private int errorCount(int percentage, int questionCount) {
 114                 int right = Math.max((percentage * questionCount) / 100, 0);
 115                 while (true) {
 116                         long resP = countPercentage(questionCount, right);
 117                         if (resP == percentage) {
 118                                 return questionCount - right;
 119                         }
 120                         if (resP > percentage) {
 121                                 return -1;
 122                         }
 123                         right++;
 124                 }
 125         }
 126
 127         private long countPercentage(int questionCount, int right) {
 128                 if (questionCount > 0 && (right * 200) % questionCount == 0) {
 129                         int floor = (right * 100) / questionCount;
 130                         if ((right * 100) % questionCount == 0) {
 131                                 return floor;
 132                         }
 133                         return floor + (floor % 2);
 134                 }
 135                 double a = (100.0 * right / questionCount);
 136                 return Math.round(a);
 137         }
 138
 139         public static void main(String[] args) {
 140                 new Thread(new javacert_vd()).start();
 141         }
 142 }