Guest User

b

a guest
Feb 6th, 2016
448
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.23 KB | None | 0 0
  1. // div1 easy
  2. import java.util.PriorityQueue;
  3.  
  4. public class FleetFunding {
  5.   static class Pair implements Comparable<Pair> {
  6.     public int end,freq;
  7.     public Pair(int end, int freq) {
  8.       this.end = end;
  9.       this.freq = freq;
  10.     }
  11.     public int compareTo(Pair other) {
  12.       return end - other.end;
  13.     }
  14.   }
  15.  
  16.   public int maxShips(int m, int[] k, int[] a, int[] b) {
  17.     int n = k.length;
  18.     int lo = 0, hi = n * 1000000;
  19.     while (lo < hi) {
  20.       int mid = (lo + hi + 1) >> 1;
  21.       boolean ok = true;
  22.       PriorityQueue<Pair> pq = new PriorityQueue<>();
  23.       for (int i = 1; i <= m; i++) {
  24.         for (int j = 0; j < n; j++) {
  25.           if (a[j] == i) {
  26.             pq.add(new Pair(b[j], k[j]));
  27.           }
  28.         }
  29.         while (pq.size() > 0 && pq.peek().end < i) pq.poll();
  30.         int need = mid;
  31.         while (need > 0 && pq.size() > 0) {
  32.           int take = Math.min(need, pq.peek().freq);
  33.           need -= take;
  34.           pq.peek().freq -= take;
  35.           if (pq.peek().freq == 0) pq.poll();
  36.         }
  37.         if (need > 0) {
  38.           ok = false;
  39.           break;
  40.         }
  41.       }
  42.      
  43.       if (ok) lo = mid;
  44.       else hi = mid-1;
  45.     }
  46.     return lo;
  47.   }
  48. }
  49.  
  50. // div1 med
  51. public class LimitedMemorySeries2 {
  52.   public static long mod = (1l << 50);
  53.   public int getSum(int n, long x0, long a, long b) {
  54.     long res = 0;
  55.     long cur = x0;
  56.     for (int i = 0; i < n; i++) {
  57.       long p1 = cur, p2 = cur;
  58.       int j1 = i, j2 = i;
  59.       while(true) {
  60.         p1 = ((p1 + mod - b) ^ a) & (mod - 1);
  61.         p2 = (((p2 ^ a) + b)) & (mod - 1);
  62.         j1--;
  63.         j2++;
  64.         if (j1 < 0 || j2 >= n || p1 >= cur || p2 >= cur) break;
  65.         res++;
  66.       }
  67.       cur = ((cur ^ a) + b) & (mod - 1);
  68.     }
  69.     return (int)(res % 1000000007);
  70.   }
  71. }
  72.  
  73. // div1 hard
  74. public class CoinFlips {
  75.   public static double getExpectation(int[] vals, int prob) {
  76.     int n = vals.length;
  77.     double p = prob / 1000000000.;
  78.    
  79.     double[] d2 = new double[n+1];
  80.     d2[0] = 1.;
  81.     for (int i = 1; i <= n; i++) {
  82.       d2[i] = d2[i-1] * (1-p);
  83.       if (d2[i] < 1e-20) d2[i] = 0;
  84.     }
  85.    
  86.     double[][] pc = new double[n+1][n+1];
  87.     double[][] ps = new double[n+1][n+1];
  88.     for (int len = 1; len <= n; len++) {
  89.       for (int idx = 1; idx <= len; idx++) {
  90.         pc[len][idx] = d2[idx-1] * p;
  91.         if (idx == 1) pc[len][idx] += d2[len];
  92.         ps[len][idx] = ps[len][idx-1] + pc[len][idx];
  93.       }
  94.     }
  95.    
  96.     double[][] dp = new double[n+2][n+2];
  97.     // [i][j] -> probability that pair i,j contributes to final answer.
  98.     for (int len = 3; len <= n; len++) {
  99.       double[][] next = new double[n+2][n+2];
  100.       for (int a1 = 1; a1 <= len; a1++) {
  101.         for (int a2 = a1+2; a2 <= len; a2++) {
  102.           next[a1][a2] = ps[len][a1-1] * dp[a1-1][a2-1]
  103.                          + (ps[len][a2-1] - ps[len][a1]) * dp[a1][a2-1]
  104.                          + (1 - ps[len][a2]) * dp[a1][a2];
  105.           if (a1+2 == a2) next[a1][a2] += pc[len][a1+1];
  106.         }
  107.       }
  108.       dp = next;
  109.     }
  110.     double ret = 0;
  111.     for (int i = 1; i <= n; i++) {
  112.       for (int j = i+2; j <= n; j++) {
  113.         ret += dp[i][j] * vals[i-1] * vals[j-1];
  114.       }
  115.     }
  116.     return ret;
  117.   }
  118. }
Add Comment
Please, Sign In to add comment