結果

問題 No.75 回数の期待値の問題
ユーザー 37zigen
提出日時 2020-03-27 01:52:28
言語 Java11
(openjdk 11.0.6)
結果
AC  
実行時間 140 ms
コード長 2,919 Byte
コンパイル時間 2,295 ms
使用メモリ 41,824 KB
最終ジャッジ日時 2020-03-27 01:52:36

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 127 ms
38,104 KB
sample2.txt AC 128 ms
38,060 KB
sample3.txt AC 129 ms
38,088 KB
sample4.txt AC 140 ms
38,076 KB
test1.txt AC 133 ms
38,064 KB
test2.txt AC 129 ms
38,060 KB
test3.txt AC 133 ms
38,076 KB
test4.txt AC 133 ms
38,128 KB
test5.txt AC 126 ms
40,076 KB
test6.txt AC 134 ms
38,112 KB
test7.txt AC 129 ms
41,784 KB
test8.txt AC 126 ms
38,068 KB
test9.txt AC 124 ms
40,088 KB
test10.txt AC 126 ms
41,824 KB
test11.txt AC 128 ms
40,132 KB
test12.txt AC 121 ms
38,096 KB
test13.txt AC 140 ms
38,068 KB
test14.txt AC 129 ms
38,096 KB
test15.txt AC 125 ms
38,072 KB
test16.txt AC 127 ms
38,104 KB
テストケース一括ダウンロード

ソースコード

diff #
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		long t = System.currentTimeMillis();
		new Main().run();
		System.err.println(System.currentTimeMillis() - t);
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int K=sc.nextInt();
		//E[i]=i進んだ状態になるために必要な回数の期待値
		//    =(E[i+1]+..+E[i+6])/6+1
		//E[i]=a[i]E[0]+b[i]
		double[] a=new double[K+1];
		double[] b=new double[K+1];
		for(int k=K-1;k>=0;--k) {
			b[k]=1;
			for(int i=1;i<=6;++i) {
				a[k]+=(k+i>K?1:a[k+i])/6;
				b[k]+=(k+i>K?0:b[k+i])/6;
			}
		}
		System.out.println(b[0]/(1-a[0]));
	}
	
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}
	
	
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
}
0