Submission #6358991

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)

	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	d := getNextInt64(scanner)

	fmt.Fprintln(writer, solve(n, d))

	writer.Flush()
}

func solve(n int, d int64) float64 {
	dp := preCalc(n, d)

	cc := make([]int, 3)

	for d%5 == 0 {
		cc[0]++
		d /= 5
	}
	for d%3 == 0 {
		cc[1]++
		d /= 3
	}
	for d%2 == 0 {
		cc[2]++
		d /= 2
	}
	if d != 1 {
		return 0.0
	}

	ans := 1.0

	for i := 0; i < 101; i++ {
		for ii := 0; ii < 101; ii++ {
			for iii := 0; iii < 201; iii++ {
				if i < cc[0] || ii < cc[1] || iii < cc[2] {
					ans -= dp[i][ii][iii]
				}
			}
		}
	}

	return ans
}

func preCalc(n int, d int64) [101][101][201]float64 {
	var dp [2][101][101][201]float64
	dp[0][0][0][0] = 1.0

	p := 0
	c := 1

	for index := 0; index < n; index++ {
		for i := 0; i <= index+1; i++ {
			for ii := 0; ii <= index+1-i; ii++ {
				for iii := 0; iii <= (index+1-i-ii)*2; iii++ {
					// 1
					dp[c][i][ii][iii] = dp[p][i][ii][iii] / 6.0
					// 2
					if iii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii][iii-1] / 6.0
					}
					// 3
					if ii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii-1][iii] / 6.0
					}
					// 4
					if iii >= 2 {
						dp[c][i][ii][iii] += dp[p][i][ii][iii-2] / 6.0
					}
					// 5
					if i > 0 {
						dp[c][i][ii][iii] += dp[p][i-1][ii][iii] / 6.0
					}
					// 6
					if ii > 0 && iii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii-1][iii-1] / 6.0
					}
				}
			}
		}
		c, p = p, c
	}

	return dp[p]
}

Submission Info

Judge Result