Submission #6358352
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 < len(dp); i++ {
for ii := 0; ii < len(dp[i]); ii++ {
for iii := 0; iii < len(dp[i][ii]); iii++ {
if i < cc[0] || ii < cc[1] || iii < cc[2] {
ans -= dp[i][ii][iii]
}
}
}
}
return ans
}
func preCalc(n int, d int64) [][][]float64 {
var dp [2][][][]float64
max := uint64(0xffffffffffffffff)
var i5, i3, i2 uint64
n5 := 1
n3 := 1
n2 := 1
for i5 = max; i5 > 0; i5 /= 5 {
n5++
}
for i3 = max; i3 > 0; i3 /= 3 {
n3++
}
for i2 = max; i2 > 0; i2 /= 2 {
n2++
}
dp[0] = make([][][]float64, n5+1)
dp[1] = make([][][]float64, n5+1)
for i := 0; i < n5+1; i++ {
dp[0][i] = make([][]float64, n3+1)
dp[1][i] = make([][]float64, n3+1)
for ii := 0; ii < n3+1; ii++ {
dp[0][i][ii] = make([]float64, n2+1)
dp[1][i][ii] = make([]float64, n2+1)
}
}
dp[0][0][0][0] = 1.0
p := 0
c := 1
for index := 0; index < n; index++ {
for i := 0; i <= n5; i++ {
for ii := 0; ii <= n3; ii++ {
for iii := 0; iii <= n2; 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
Submission Time |
|
Task |
D - サイコロ |
User |
ccppjsrb |
Language |
Go (1.6) |
Score |
0 |
Code Size |
2747 Byte |
Status |
WA |
Exec Time |
362 ms |
Memory |
2304 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
111 ms |
2304 KB |
01 |
WA |
298 ms |
2304 KB |
02 |
WA |
272 ms |
2304 KB |
03 |
AC |
124 ms |
2304 KB |
04 |
AC |
121 ms |
2304 KB |
05 |
WA |
325 ms |
2304 KB |
06 |
WA |
294 ms |
2304 KB |
07 |
WA |
279 ms |
2304 KB |
08 |
AC |
60 ms |
2304 KB |
09 |
WA |
268 ms |
2304 KB |
10 |
AC |
362 ms |
2304 KB |
90 |
AC |
10 ms |
2304 KB |
91 |
AC |
13 ms |
2304 KB |