LATTICE - Distance on a square lattice

Let L to be an n×n square lattice, you can consider its points as (x, y), where x and y are integers from the [1, n] interval. And let f(n) to be the expected distance between two not necessarily distinct points on the lattice. For example f(1)=0 and f(2)=(2 + √ 2  ) / 4.

Input

There is no input.

Output

5000 lines, on the n-th line give the value of f(n) by 2 digits after the decimal point.

Example

Input:
No input.

Output:
0.00
0.85
1.45
2.01
2.55
.
.
.
2607.03

Added by:Robert Gerbicz
Date:2009-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST VB.NET WHITESPACE
Resource:own resource

hide comments
2013-04-03 01:03:02 Zhouxing Shi
not neccesserily but necessarily.

Last edit: 2013-11-17 11:45:07
2011-10-16 14:50:30 Anshul Gupta
Getting WA :((
though my output for f(5000) is correct!!
plz hlp
2010-03-04 13:10:23 :D
I pretty sure that I was using O(N^2) algo for this one. O(N^3) would probably take minutes to execute.
2010-02-04 21:10:54 Miguel Oliveira
Is it possible to solve this problem faster than O(N^3)?
2009-08-27 00:22:22 Jesse Millikan
I can't even tell what the question is. The writer doesn't describe f(n) in terms of n. Edit: I read *awesome*. n is the size of the lattice...

Last edit: 2009-08-27 15:07:46
2009-05-26 13:58:31 Alvaro Lara
I thinks there is really no way to solve efficiently this problem. Mainly because the nature is exponential :S
2009-04-08 04:23:03 [Trichromatic] XilinX
I think the author allows any right algorithm(even though they are very slow) to solve this problem.
2009-04-08 01:23:58 Eigenray
Why not double the time limit and allow other languages?
Edit: I guess that's not a bad thing. Would it make more sense as a partial problem?

Last edit: 2009-04-08 05:00:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.