SPOJ BTCODE_H (Maths) Solution - Java

Test Case given-

N = 2, K = 2.

# of words containing only 0 and 1 that are of length 2 -> 4

00
01
10
11

Now insertion of words may happen as:

00 00                      
00 01           01 00
00 10           10 00
00 11           11 00

01 01      
01 10           10 01
01 11           11 01

10 10
10 11           11 10

11 11

Total # cases -> 16.

# cases where trie has 3 nodes = 4
                                4 nodes = 4
                                5 nodes = 8

Expected value of the number of nodes ->

(3*4 + 4*4 + 5*8)                                    68
----------------------         =             ---------------------             =              4.25
          16                                                16

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class BTCODE_HSimple {
    
    //Exponentiation by Repeated Sqauring
    public static double power(double a, int b){
        if(b==0)return 1;
        if(b==1)return a;
        if(b%2==1){
            return a*power(a*a, (b-1)/2);
        }else return power(a*a, b/2);
    }
    
    public static void main(String[] args){
        int n = IO.nextInt(); 
        while(n-->0){
            int N = IO.nextInt();
            int K = IO.nextInt();
            double ans = 1;
            for(int i=1;i<=K;++i){
                double p = power(0.5, i); 
                ans += 1;
                double op = 1-p; 
                for(int j=1;j<N;++j){ 
                    ans += power(op, j);
                } 
            }
            System.out.printf("%.2f\n", ans);
        }
    }



    /**************************************IO**************************************/
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}