Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // div1 easy
- import java.util.PriorityQueue;
- public class FleetFunding {
- static class Pair implements Comparable<Pair> {
- public int end,freq;
- public Pair(int end, int freq) {
- this.end = end;
- this.freq = freq;
- }
- public int compareTo(Pair other) {
- return end - other.end;
- }
- }
- public int maxShips(int m, int[] k, int[] a, int[] b) {
- int n = k.length;
- int lo = 0, hi = n * 1000000;
- while (lo < hi) {
- int mid = (lo + hi + 1) >> 1;
- boolean ok = true;
- PriorityQueue<Pair> pq = new PriorityQueue<>();
- for (int i = 1; i <= m; i++) {
- for (int j = 0; j < n; j++) {
- if (a[j] == i) {
- pq.add(new Pair(b[j], k[j]));
- }
- }
- while (pq.size() > 0 && pq.peek().end < i) pq.poll();
- int need = mid;
- while (need > 0 && pq.size() > 0) {
- int take = Math.min(need, pq.peek().freq);
- need -= take;
- pq.peek().freq -= take;
- if (pq.peek().freq == 0) pq.poll();
- }
- if (need > 0) {
- ok = false;
- break;
- }
- }
- if (ok) lo = mid;
- else hi = mid-1;
- }
- return lo;
- }
- }
- // div1 med
- public class LimitedMemorySeries2 {
- public static long mod = (1l << 50);
- public int getSum(int n, long x0, long a, long b) {
- long res = 0;
- long cur = x0;
- for (int i = 0; i < n; i++) {
- long p1 = cur, p2 = cur;
- int j1 = i, j2 = i;
- while(true) {
- p1 = ((p1 + mod - b) ^ a) & (mod - 1);
- p2 = (((p2 ^ a) + b)) & (mod - 1);
- j1--;
- j2++;
- if (j1 < 0 || j2 >= n || p1 >= cur || p2 >= cur) break;
- res++;
- }
- cur = ((cur ^ a) + b) & (mod - 1);
- }
- return (int)(res % 1000000007);
- }
- }
- // div1 hard
- public class CoinFlips {
- public static double getExpectation(int[] vals, int prob) {
- int n = vals.length;
- double p = prob / 1000000000.;
- double[] d2 = new double[n+1];
- d2[0] = 1.;
- for (int i = 1; i <= n; i++) {
- d2[i] = d2[i-1] * (1-p);
- if (d2[i] < 1e-20) d2[i] = 0;
- }
- double[][] pc = new double[n+1][n+1];
- double[][] ps = new double[n+1][n+1];
- for (int len = 1; len <= n; len++) {
- for (int idx = 1; idx <= len; idx++) {
- pc[len][idx] = d2[idx-1] * p;
- if (idx == 1) pc[len][idx] += d2[len];
- ps[len][idx] = ps[len][idx-1] + pc[len][idx];
- }
- }
- double[][] dp = new double[n+2][n+2];
- // [i][j] -> probability that pair i,j contributes to final answer.
- for (int len = 3; len <= n; len++) {
- double[][] next = new double[n+2][n+2];
- for (int a1 = 1; a1 <= len; a1++) {
- for (int a2 = a1+2; a2 <= len; a2++) {
- next[a1][a2] = ps[len][a1-1] * dp[a1-1][a2-1]
- + (ps[len][a2-1] - ps[len][a1]) * dp[a1][a2-1]
- + (1 - ps[len][a2]) * dp[a1][a2];
- if (a1+2 == a2) next[a1][a2] += pc[len][a1+1];
- }
- }
- dp = next;
- }
- double ret = 0;
- for (int i = 1; i <= n; i++) {
- for (int j = i+2; j <= n; j++) {
- ret += dp[i][j] * vals[i-1] * vals[j-1];
- }
- }
- return ret;
- }
- }
Add Comment
Please, Sign In to add comment