NEERC/javacert/javacert_mb.java

   1 import java.io.FileReader;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.Arrays;
   5 import java.util.Scanner;
   6
   7 public class javacert_mb implements Runnable {
   8     private Scanner in;
   9     private PrintWriter out;
  10     private int totalCorrect;
  11     private int totalQuest;
  12     private int numCateg;
  13     private int[] correctPercentage;
  14     private int bestDiff;
  15     private int[] bestCorrect;
  16     private int[] bestQuest;
  17     private int lowerBound[][];
  18     private int upperBound[][];
  19
  20     public static void main(String[] args) {
  21         new Thread(new javacert_mb()).start();
  22     }
  23
  24     private static final int INFINITY = 1000000;
  25
  26     public void run() {
  27         try {
  28             in = new Scanner(new FileReader("javacert.in"));
  29             out = new PrintWriter("javacert.out");
  30
  31             solve();
  32
  33             in.close();
  34             out.close();
  35         } catch (IOException e) {
  36             e.printStackTrace();
  37         }
  38     }
  39
  40     private int getPercentage(int part, int total) {
  41         int quot = (100 * part) / total;
  42         int rem = (100 * part) % total;
  43         if (2 * rem == total) {
  44             return quot % 2 == 0 ? quot : quot + 1;
  45         } else if (2 * rem < total) {
  46             return quot;
  47         } else {
  48             return quot + 1;
  49         }
  50     }
  51
  52     private int getLowerBound(int total, int percentage) {
  53         int guess = total * (percentage - 1) / 100;
  54         while (getPercentage(guess, total) < percentage) {
  55             guess++;
  56         }
  57         return guess;
  58     }
  59
  60     private int getUpperBound(int total, int percentage) {
  61         int guess = total * (percentage + 1) / 100;
  62         while (getPercentage(guess, total) > percentage) {
  63             guess--;
  64         }
  65         return guess;
  66     }
  67
  68     private void solve() {
  69         totalCorrect = in.nextInt();
  70         totalQuest = in.nextInt();
  71         numCateg = in.nextInt();
  72         correctPercentage = new int[numCateg];
  73         for (int i = 0; i < numCateg; i++) {
  74             correctPercentage[i] = in.nextInt();
  75         }
  76
  77         int[][][] opt = new int[numCateg + 1][totalQuest + 1][totalCorrect + 1];
  78         int[][][] backQuest = new int[numCateg + 1][totalQuest + 1][totalCorrect + 1];
  79         int[][][] backCorrect = new int[numCateg + 1][totalQuest + 1][totalCorrect + 1];
  80         for (int i = 0; i <= totalQuest; i++) {
  81             Arrays.fill(opt[0][i], INFINITY);
  82         }
  83         opt[0][0][0] = 0;
  84
  85         lowerBound = new int[totalQuest + 1][101];
  86         upperBound = new int[totalQuest + 1][101];
  87         for (int i = 1; i <= totalQuest; i++) {
  88             for (int j = 0; j <= 100; j++) {
  89                 lowerBound[i][j] = getLowerBound(i, j);
  90                 upperBound[i][j] = getUpperBound(i, j);
  91             }
  92         }
  93
  94         bestDiff = INFINITY;
  95         bestQuest = new int[numCateg];
  96         bestCorrect = new int[numCateg];
  97         for (int low = 1; low <= totalQuest / numCateg + 1; low++) {
  98             for (int categ = 0; categ < numCateg; categ++) {
  99                 for (int curQuest = 0; curQuest <= totalQuest; curQuest++) {
 100                     for (int curCorrect = 0; curCorrect <= totalCorrect; curCorrect++) {
 101                         int bestDiff = INFINITY;
 102                         int bestQuest = -1;
 103                         int bestCorrect = -1;
 104                         for (int thisQuest = low; thisQuest <= curQuest; thisQuest++) {
 105                             final int lowCorrect = lowerBound[thisQuest][correctPercentage[categ]];
 106                             final int upperCorrect = Math.min(upperBound[thisQuest][correctPercentage[categ]], curCorrect);
 107                             for (int thisCorrect = lowCorrect; thisCorrect <= upperCorrect; thisCorrect++) {
 108                                 int thisDiff = Math.max(
 109                                         opt[categ][curQuest - thisQuest][curCorrect - thisCorrect],
 110                                         thisQuest - low);
 111                                 if (thisDiff < bestDiff) {
 112                                     bestDiff = thisDiff;
 113                                     bestQuest = thisQuest;
 114                                     bestCorrect = thisCorrect;
 115                                 }
 116                             }
 117                         }
 118                         opt[categ + 1][curQuest][curCorrect] = bestDiff;
 119                         backQuest[categ + 1][curQuest][curCorrect] = bestQuest;
 120                         backCorrect[categ + 1][curQuest][curCorrect] = bestCorrect;
 121                     }
 122                 }
 123             }
 124
 125             if (opt[numCateg][totalQuest][totalCorrect] < bestDiff) {
 126                 bestDiff = opt[numCateg][totalQuest][totalCorrect];
 127
 128                 int curQuest = totalQuest;
 129                 int curCorrect = totalCorrect;
 130                 for (int categ = numCateg - 1; categ >= 0; categ--) {
 131                     bestQuest[categ] = backQuest[categ + 1][curQuest][curCorrect];
 132                     bestCorrect[categ] = backCorrect[categ + 1][curQuest][curCorrect];
 133                     curQuest -= bestQuest[categ];
 134                     curCorrect -= bestCorrect[categ];
 135                 }
 136
 137                 assert curQuest == 0;
 138                 assert curCorrect == 0;
 139             }
 140         }
 141
 142         for (int i = 0; i < numCateg; i++) {
 143             out.printf("%d %d\n", bestQuest[i] - bestCorrect[i], bestQuest[i]);
 144         }
 145     }
 146
 147 }