package main import ( "bufio" "bytes" "fmt" "io" "os" "strconv" ) // ----------------------------------------------------------------------------- // IO helper functions // Returns next token from input. It must be initialized by SetInput() // before the first call. var nextToken func() ([]byte, error) var nextLine func() ([]byte, error) // Holds a buffer for output. It must be initialized by SetOutput(). // All IO fucntions (read*() and [e]print*()) should write to OutputWriter // instead of this. var OutputBuffer *bufio.Writer // Holds an io.Writer. It must be initialized by SetOutput() var OutputWriter io.Writer // Set IO functions for interactive input/output. func SetInteractive(w io.Writer, r io.Reader) { SetUnbefferedInput(r) OutputBuffer = nil OutputWriter = w } // Setup OutputBuffer and OutputWriter. func SetOutput(w io.Writer) { OutputBuffer = bufio.NewWriter(w) OutputWriter = OutputBuffer } // Flushes OutputBuffer func Flush() { if OutputBuffer != nil { OutputBuffer.Flush() } } // Returns true if c is a white space func IsSpace(c byte) bool { switch c { case '\t', '\n', '\v', '\f', '\r', ' ': return true } return false } func IsNewLine(c byte) bool { switch c { case '\n', '\r': return true } return false } // Setup nextToken with input buffer. func SetInput(r io.Reader) { buf := new(bytes.Buffer) var b []byte var i int rest := func() ([]byte, error) { for i < len(b) && IsSpace(b[i]) { i++ } if i == len(b) { return nil, io.ErrUnexpectedEOF } j := i for i < len(b) && !IsSpace(b[i]) { i++ } return b[j:i], nil } initial := func() ([]byte, error) { io.Copy(buf, r) b = buf.Bytes() nextToken = rest return rest() } nextToken = initial restLn := func() ([]byte, error) { for i < len(b) && IsNewLine(b[i]) { i++ } if i == len(b) { return nil, io.ErrUnexpectedEOF } j := i for i < len(b) && !IsNewLine(b[i]) { i++ } return b[j:i], nil } initialLn := func() ([]byte, error) { io.Copy(buf, r) b = buf.Bytes() nextLine = restLn return restLn() } nextLine = initialLn } // Setup nextToken without input buffer. func SetUnbefferedInput(r io.Reader) { buf := bufio.NewReader(r) var b []byte var i int nextToken = func() ([]byte, error) { var err error if i == len(b) { b, err = buf.ReadBytes('\n') if err != nil { return nil, err } i = 0 j := len(b) - 1 for 0 <= j && IsSpace(b[j]) { j-- } b = b[0 : j+1] } for i < len(b) && IsSpace(b[i]) { i++ } j := i for i < len(b) && !IsSpace(b[i]) { i++ } if i == j { return nil, io.ErrUnexpectedEOF } return b[j:i], nil } } // ----------------------------------------------------------------------------- // IO functions // Reads next token and return it as []byte func readb() []byte { b, err := nextToken() if err != nil { panic(err) } return b } // Reads next token and return it as string func reads() string { return string(readb()) } // Read next line as []byte func readbln() []byte { b, err := nextLine() if err != nil { panic(err) } return b } // Read next line as string func readsln() string { return string(readbln()) } // Reads next token and return it as int64 func readll() int64 { i, err := strconv.ParseInt(reads(), 10, 64) if err != nil { panic(err.Error()) } return i } // Reads next token and return it as int func readi() int { return int(readll()) } // Reads next token and return it as float64 func readf() float64 { f, err := strconv.ParseFloat(reads(), 64) if err != nil { panic(err.Error()) } return f } // Write args to OutputWriter with the format f func printf(f string, args ...interface{}) (int, error) { return fmt.Fprintf(OutputWriter, f, args...) } // Write args to OutputWriter without format func println(args ...interface{}) (int, error) { return fmt.Fprintln(OutputWriter, args...) } // Write args to stderr with the format f func eprintf(f string, args ...interface{}) (int, error) { return fmt.Fprintf(os.Stderr, f, args...) } // Write args to stderr without format func eprintln(args ...interface{}) (int, error) { return fmt.Fprintln(os.Stderr, args...) } // ----------------------------------------------------------------------------- // Simple math functions const ( // big prime INF = 1000000007 INF2 = 1000000009 INF3 = 998244353 ) func min(a, b int) int { if a < b { return a } return b } func minll(a, b int64) int64 { if a < b { return a } return b } func max(a, b int) int { if a < b { return b } return a } func maxll(a, b int64) int64 { if a < b { return b } return a } func abs(a int) int { if a < 0 { return -a } return a } func absll(a int64) int64 { if a < 0 { return -a } return a } // egcd(a, b) returns d, x, y: // d is gcd(a,b) // x, y are integers that satisfy ax + by = d func egcd(a, b int) (int, int, int) { if b == 0 { return a, 1, 0 } d, x, y := egcd(b, a%b) return d, y, x - a/b*y } func egcdll(a, b int64) (int64, int64, int64) { if b == 0 { return a, 1, 0 } d, x, y := egcdll(b, a%b) return d, y, x - a/b*y } func gcd(a, b int) int { d, _, _ := egcd(a, b) return d } func gcdll(a, b int64) int64 { d, _, _ := egcdll(a, b) return d } // set up IO functions func init() { // for non-interactive SetInput(os.Stdin) SetOutput(os.Stdout) // Enable below when interactive. Its ok to leave above intact. // SetInteractive(os.Stdout, os.Stdin) } func main() { defer Flush() N := readi() A := make([]int, N) B := make([]int, N) for i := range A { A[i] = readi() } for i := range B { B[i] = readi() } var win, count int DoPermutation0n(N, func(a []int) { DoPermutation0n(N, func(b []int) { count++ w := 0 for k := range a { i := a[k] j := b[k] if B[j] < A[i] { w++ } } if N-w < w { win++ } }) }) printf("%8f\n", float64(win)/float64(count)) } // Heap's algorithm func DoPermutation(a []int, fn func([]int)) { n := len(a) c := make([]int, n) i := 0 swap := func(i, j int) { a[i], a[j] = a[j], a[i] } fn(a) for i < n { if c[i] < i { if i%2 == 0 { swap(0, i) } else { swap(c[i], i) } fn(a) c[i]++ i = 0 } else { c[i] = 0 i++ } } } func DoPermutation0n(n int, fn func([]int)) { a := make([]int, n) for i := range a { a[i] = i } DoPermutation(a, fn) } func next_permutation(a []int) chan []int { ch := make(chan []int) go func() { DoPermutation(a, func(x []int) { ch <- x }) close(ch) }() return ch }