fork download
copy 
  1. // Errichto
  2.  
  3. // Div1-Easy
  4. public class BearCavalry {
  5.     public int countAssignments(int[] warriors, int[] horses) {
  6.         final int mod = 1000 * 1000 * 1000 + 7;
  7.         int n = warriors.length;
  8.         Arrays.sort(warriors, 1, n);
  9.         long ans = 0;
  10.         for(int assign = 0; assign < n; ++assign) {
  11.             int strenghtLimit = warriors[0] * horses[assign];
  12.             int h2[] = new int[n - 1];
  13.             for(int i = 0; i < assign; ++i) h2[i] = horses[i];
  14.             for(int i = assign + 1; i < n; ++i) h2[i-1] = horses[i];
  15.             Arrays.sort(h2);
  16.             int h2Pointer = 0;
  17.             long m = 1;
  18.             for(int i = n - 1; i >= 1; --i) {
  19.                 while(h2Pointer < h2.length && warriors[i] * h2[h2Pointer] < strenghtLimit)
  20.                     ++h2Pointer;
  21.                 m = m * (h2Pointer - (n-1 - i)) % mod;
  22.             }
  23.             ans = (ans + m) % mod;
  24.         }
  25.         return (int) ans;
  26.     }
  27. }
  28.  
  29. // Div1-Med
  30. public class BearPermutations {
  31.     public int countPermutations(int N, int S, int mod) {
  32.         long bin[][] = new long[N+1][N+1];
  33.         for(int i = 0; i <= N; ++i) {
  34.             bin[i][0] = 1;
  35.             for(int j = 1; j <= i; ++j)
  36.                 bin[i][j] = (bin[i-1][j-1] + bin[i-1][j]) % mod;
  37.         }
  38.  
  39.         // dp[n][where][s]
  40.         long dp[][][] = new long[N+1][N+1][S+1];
  41.         long left[][] = new long[N+1][S+1];
  42.  
  43.         dp[1][1][0] = 1;
  44.  
  45.         for(int n = 1; n <= N; ++n) {
  46.             // where the smallest/biggest number goes
  47.             for(int where = 1; where <= n; ++where) {
  48.                 if(where == 1 || where == n) {
  49.                     for(int where0 = 1; where0 <= n - 1; ++where0)
  50.                         for(int s = 0; s <= S; ++s) {
  51.                             dp[n][where][s] += dp[n-1][where0][s];
  52.                             dp[n][where][s] %= mod;
  53.                         }
  54.                 }
  55.                 else {
  56.                     int n1 = where - 1;
  57.                     int n2 = n - where;
  58.                     for(int s1 = 0; s1 <= S; ++s1)
  59.                         for(int s2 = 0; s2 <= S - s1; ++s2) {
  60.                             dp[n][where][s1+s2] += left[n1][s1] * left[n2][s2] % mod * bin[n1+n2][n1];
  61.                             dp[n][where][s1+s2] %= mod;
  62.                         }
  63.                 }
  64.                 for(int s = 0; s+where <= S; ++s) {
  65.                     left[n][s+where] += dp[n][where][s];
  66.                     left[n][s+where] %= mod;
  67.                 }
  68.             }
  69.         }
  70.         long ans = 0;
  71.         for(int where = 1; where <= N; ++where)
  72.             for(int s = 0; s <= S; ++s)
  73.                 ans += dp[N][where][s];
  74.         ans %= mod;
  75.         return (int) ans;
  76.     }
  77. }
  78.  
  79. // Div1-Hard
  80. public class BearGirls {
  81.     public double expectedValue(int[] A, int[] T, int cost) {
  82.         int n = 0;
  83.         for(int i = 0; i < T.length; ++i)
  84.             n += T[i];
  85.         int[] t = new int[n];
  86.         int iii = 0;
  87.         for(int i = 0; i < A.length; ++i)
  88.             for(int j = 0; j < T[i]; ++j)
  89.                 t[iii++] = A[i] + j;
  90.         // f(k, r) is the expected value of the r-th biggest number from k randomly selected values from the input
  91.         // f(k,r) = p * f(k+1,r+1) + (1-p) * f(k+1,r)
  92.         // where p = r/(k+1)
  93.         Arrays.sort(t);
  94.         double[] smart = new double[n+1], stupid = new double[n+1];
  95.         for(int i = 1; i <= n; ++i)
  96.             smart[i] = stupid[i] = t[i-1];
  97.         for(int k = n-1; k >= 1; --k) {
  98.             double nxt = 0;
  99.             for(int i = 1; i <= k + 1; ++i)
  100.                 nxt += smart[i] / (k + 1);
  101.             for(int i = 1; i <= k; ++i) {
  102.                 double p = i / (k + 1.);
  103.                 stupid[i] = p * stupid[i+1] + (1-p) * stupid[i];
  104.                 smart[i] = Math.max(nxt-cost, stupid[i]);
  105.             }
  106.         }
  107.         return smart[1] - cost;
  108.     }
  109. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class BearCavalry is public, should be declared in a file named BearCavalry.java
public class BearCavalry {
       ^
Main.java:30: error: class BearPermutations is public, should be declared in a file named BearPermutations.java
public class BearPermutations {
       ^
Main.java:80: error: class BearGirls is public, should be declared in a file named BearGirls.java
public class BearGirls {
       ^
Main.java:8: error: cannot find symbol
        Arrays.sort(warriors, 1, n);
        ^
  symbol:   variable Arrays
  location: class BearCavalry
Main.java:15: error: cannot find symbol
            Arrays.sort(h2);
            ^
  symbol:   variable Arrays
  location: class BearCavalry
Main.java:93: error: cannot find symbol
        Arrays.sort(t);
        ^
  symbol:   variable Arrays
  location: class BearGirls
6 errors
stdout
copy 
Standard output is empty
https://ideone.com/9XTojx
SRM #673 Div1
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!