Advertisement
Guest User

TC2014_1C_950

a guest
Apr 26th, 2014
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.48 KB | None | 0 0
  1. import java.math.BigInteger;
  2.  
  3. public class RedPaint {
  4.     static BigInteger[]fib;
  5.     static long counter = 0L;
  6.     private static BigInteger factorial(int n) {
  7.         BigInteger val = BigInteger.valueOf(1L);
  8.         for (int i = 2; i <= n ; i++) {
  9.             val = val.multiply(BigInteger.valueOf(i));
  10.         }
  11.         return val;
  12.     }
  13.    
  14.     public double expectedCells(int N) {
  15.         int k = N;
  16.         N = (k % 2 == 0)?k:k+1;
  17.         BigInteger res = factorial(N).divide(factorial(N / 2));
  18.         BigInteger res1 = BigInteger.valueOf(0);
  19.         if (k%2 != 0){
  20.             res1 = factorial(N - 2).divide(factorial((N - 2) / 2));
  21.             res1 = res1.divide(factorial((N - 2) / 2));
  22.         }
  23.         res = res.divide(factorial(N / 2));
  24.         double sol = res.doubleValue() / power(2,N).doubleValue();
  25.         double sl2 = 0.0;
  26.         if (k % 2 != 0){
  27.             sl2 = res1.doubleValue() / power(2,(N - 2)).doubleValue();
  28.             sol = (k + 1)*sol + (k)*sl2;
  29.         }
  30.         else
  31.         sol = sol*N + sol*( N + 1);
  32.         return sol;
  33.     }
  34.  
  35.     private BigInteger power(int i, int n) {
  36.         BigInteger big = BigInteger.valueOf(1);
  37.         BigInteger exp = BigInteger.valueOf(2);
  38.         while (n > 0){
  39.             if (n % 2 == 0){
  40.                 exp = exp.multiply(exp);
  41.                 n /= 2;
  42.             }
  43.             else {
  44.                 n -=1;
  45.                 big = big.multiply(exp);
  46.             }
  47.         }
  48.         return big;
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement