HS09SHIP - Starship

no tags 

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

hide comments
Francky: 2017-02-10 18:03:36

Now doable using python.

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-09 17:08:07

I still don't have an O(n) solution, but by avoiding repeated calculation (without precomputation) O(n^2) can get AC under 2s...

Last edit: 2012-12-09 17:32:07
Robert Gerbicz: 2012-12-09 14:00:02

Ok, now I think it is correct. The only small issue is that it is now displaying 0 instead of accepted, but on the best solutions page it is correct.

(You have to solve all tests to get AC.)

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-09 13:53:48

finally, 10pts with O(n^2) algo + fast I/O... and O(n^3) + fast I/O still get 4pts in C...

:D: 2012-12-09 13:53:48

I moved it to challenge, beause with current settings it's scored like a challenge problem. Robert, change the setting and rejudge. Then we can move it to classical.

Last edit: 2012-12-07 08:32:00
Aditya Pande: 2012-12-09 13:53:48

@Robert Gerbicz: can you please suggest how my submission can be made faster. Right now i got AC in 5.3 seconds

Robert Gerbicz: 2012-12-09 13:53:48

"and leave it in classical" when checked it was in challenge. Moved back to classical.

:D: 2012-12-09 13:53:48

Yes, I know. For now the author isn't responding to my e-mails. I'll make an exception here and leave it in classical. It's pretty much broken this way, because you probably get the same number of points, no matter how much you score here.

Vikas Kushwaha: 2012-12-09 13:53:48

this is not a kind of problem that is to be left without points.
feeling bad as i wasted many hours in thinking the solution to this problem.

:D: 2012-12-09 13:53:48

It's determined by the scoring. Classical are only AC or some error. For partials you get a fraction pass-rates depending on how many test files you clear. Partials are unfortunately left without scores. I contacted problem author about it.


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