NEERC/javacert/gen_stress_javacert.java

   1 import java.util.*;
   2
   3 public class gen_stress_javacert {
   4
   5         public static void main(String[] args) throws Exception {
   6                 new gen_stress_javacert().go();
   7         }
   8
   9         void go() throws Exception {
  10                 stress();
  11         }
  12
  13         int k;
  14         int n;
  15         int m;
  16         int[] p;
  17
  18         static class Pair {
  19                 int wi;
  20                 int ni;
  21
  22                 Pair(int wi, int ni) {
  23                         this.wi = wi;
  24                         this.ni = ni;
  25                 }
  26
  27                 @Override
  28                 public String toString() {
  29                         return wi + " " + ni + " " + (100.0*(ni - wi) / ni);
  30                 }
  31         }
  32
  33         int w;
  34         List<List<Pair>> llpall = new ArrayList<List<Pair>>();
  35         List<List<Pair>> llp = new ArrayList<List<Pair>>();
  36         int soldiff;
  37         int maxsteps;
  38
  39         Random rnd = new Random();
  40
  41         void stress() {
  42                 n = 100;
  43                 m = 10;
  44                 wi = new int[m];
  45                 ni = new int[m];
  46                 p = new int[m];
  47                 prebuildPairs();
  48                 presortPairs();
  49                 while (true) {
  50                         checkOne();
  51                 }
  52         }
  53
  54         long timelimit;
  55
  56         private void checkOne() {
  57                 randomSol();
  58                 selectPairs();
  59                 soldiff = Integer.MAX_VALUE;
  60                 long time = System.currentTimeMillis();
  61                 timelimit = time + 10000L;
  62                 int steps = find(0, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
  63                 time = System.currentTimeMillis() - time;
  64                 assert soldiff < Integer.MAX_VALUE;
  65                 if (steps > maxsteps) {
  66                         System.out.println();
  67                         System.out.printf("%d %d %d%n", k, n, m);
  68                         for (int i = 0; i < m; i++) {
  69                                 System.out.printf("%d %d %d%n", p[i], wi[i], ni[i]);
  70                         }
  71                         System.out.printf("%d steps in %d ms%n", steps, time);
  72                         maxsteps = steps;
  73                 } else
  74                         System.out.println(".");
  75         }
  76
  77         int[] wi;
  78         int[] ni;
  79
  80         private void randomSol() {
  81                 int ns = 0;
  82                 w = 0;
  83                 int epr = rnd.nextInt(20);
  84                 for (int i = 0; i < m; i++) {
  85                         int rem = m - i - 1;
  86                         ni[i] = rem == 0 ? n - ns :
  87                                 rnd.nextInt(10) > epr ? Math.min(n - ns - rem, Math.round(n / m)) :
  88                                 1 + rnd.nextInt(n - ns - rem);
  89                         wi[i] = rnd.nextInt(ni[i] + 1);
  90                         p[i] = (int)Math.round(100.0 * (ni[i] - wi[i]) / ni[i]);
  91                         ns += ni[i];
  92                         w += wi[i];
  93                 }
  94                 k = n - w;
  95         }
  96
  97
  98
  99         private void selectPairs() {
 100                 llp.clear();
 101                 for (int i = 0; i < m; i++) {
 102                         llp.add(llpall.get(p[i]));
 103                 }
 104         }
 105
 106         private void prebuildPairs() {
 107                 for (int i = 0; i <= n; i++) {
 108                         llpall.add(new ArrayList<Pair>());
 109                 }
 110                 for (int ni = 1; ni <= n; ni++) {
 111                         for (int wi = 0; wi <= ni; wi++) {
 112                                 int ppp = 100 * (ni - wi);
 113                                 int pp = (2 * ppp + ni) / (2 * ni);
 114                                 if (2 * ppp % ni == 0 && 2 * ppp / ni % 2 == 1 && pp % 2 == 1)
 115                                         pp--;
 116                                 llpall.get(pp).add(new Pair(wi, ni));
 117                         }
 118                 }
 119         }
 120
 121         private void presortPairs() {
 122                 final double mid = n / m;
 123                 for (int i = 0; i <= n; i++) {
 124                     Collections.sort(llpall.get(i), new Comparator<Pair>() {
 125                             public int compare(Pair p1, Pair p2) {
 126                                     double d1 = Math.abs(p1.ni - mid);
 127                                     double d2 = Math.abs(p2.ni - mid);
 128                                     return Double.compare(d1, d2);
 129                             }
 130                     });
 131                 }
 132         }
 133
 134         int find(int i, int ws, int ns, int minni, int maxni) {
 135                 if (ns > n || ws > w)
 136                         return 1;
 137                 int diff = maxni - minni;
 138                 if (diff >= soldiff)
 139                         return 1;
 140                 if (i == m) {
 141                         if (ns < n || ws < w)
 142                                 return 1;
 143                         soldiff = diff;
 144                         return 1;
 145                 }
 146                 if (System.currentTimeMillis() > timelimit)
 147                         return 1;
 148                 int res = 0;
 149                 for (Pair p : llp.get(i)) {
 150                         res += find(i + 1, ws + p.wi, ns + p.ni, Math.min(minni, p.ni), Math.max(maxni, p.ni));
 151                 }
 152                 return res;
 153         }
 154 }