HS09SHIP - Starship

You are traveling by starship and at any time you are always moving in one of 6 directions: forwards, backwards, up, down, left, or right. In other words, during every second, one of the three coordinates of your position changes by exactly one unit. Let us suppose that you are at (x1, y1, z1) and you would like to reach (x2, y2, z2). Unfortunately, yours is only a first generation starship, which means that all movements are completely random, so at every second you will be moving with probability 1/6 forwards/backwards/up/down/left/right. Could you compute the probability that we will be at the destination in the n-th second?

Input

The first line contains integer T, representing the number of test cases. Each test case starts with a positive integer n, the next line gives the starting position of the starship, while the final one is the destination. It is known that: T < 30000, 0 < n <= 1000. The absolute value of the x, y, z coordinates are smaller than 106. There are 5 input sets for 10 points.

Output

T lines, and in the i-th line give the required probability for the i-th test case. Use 10 digits after the decimal point!

Example

Input:
5
2
0 0 0
0 0 0
4
0 0 0
0 0 0
100
2 -3 4
-4 5 6
100
2 -3 4
-4 5 7
1000
0 0 0
0 0 0

Output:
0.1666666667
0.0694444444
0.0001389381
0.0000000000
0.0000208505

Added by:Robert Gerbicz
Date:2009-09-07
Time limit:1s-1.148s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:High School Programming League

hide comments
2012-12-09 13:53:48 Aditya Pande
what does it mean if a problem is partial?
2012-12-09 13:53:48 Abhishek Modi
@Aditya You can use log to prevent overflow
2012-12-09 13:53:48 Aditya Pande
how to handle precision/ overflowing
getting TLE?

Last edit: 2012-12-03 08:34:18
2012-12-09 13:53:48 Vikas Kushwaha
done with O(n^2) method.
trying for O(n) now...
2012-12-09 13:53:48 Francky
I think I too have a O(n) solution, but I'm very poor in dealing floats, another chapter to learn.
Edit : I think I already hate floats ... Arghhh
Edit2 : Gnnn, it was signed int, gnnnn
(8 points with python )

Last edit: 2012-12-02 19:38:49
2012-12-09 13:53:48 Mitch Schwartz
I found an O(n) solution, but actually O(n^2) can pass too.
re (author): That's nice, the official solution runs in O(n^2) time.

Last edit: 2012-12-02 12:08:58
2012-12-09 13:53:48 Aditya Pande
why am i getting 0 limit 2??
Edit:
Nevermind got it


Last edit: 2012-12-02 08:14:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.