Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem B
Squeeze the Cylinders

Laid on the flat ground in the stockyard are a number of heavy metal cylinders with (possibly) different diameters but with the same length. Their ends are aligned and their axes are oriented to exactly the same direction.

We'd like to minimize the area occupied. The cylinders are too heavy to lift up, although rolling them is not too difficult. So, we decided to push the cylinders with two high walls from both sides.

Your task is to compute the minimum possible distance between the two walls when cylinders are squeezed as much as possible. Cylinders and walls may touch one another. They cannot be lifted up from the ground, and thus their order cannot be altered.

Figure B.1. Cylinders between two walls

Input

The input consists of a single test case. The first line has an integer $N$ $(1 \leq N \leq 500)$, which is the number of cylinders. The second line has $N$ positive integers at most 10,000. They are the radii of cylinders from one side to the other.

Output

Print the distance between the two walls when they fully squeeze up the cylinders. The number should not contain an error greater than 0.0001.

Sample Input 1

2
10 10

Sample Output 1

40.00000000

Sample Input 2

2
4 12

Sample Output 2

29.85640646

Sample Input 3

5
1 10 1 10 1

Sample Output 3

40.00000000

Sample Input 4

3
1 1 1

Sample Output 4

6.00000000

Sample Input 5

2
5000 10000

Sample Output 5

29142.13562373

The following figures correspond to the Sample 1, 2, and 3.



Sample input:
2
10 10


Sample output:
40.00000000

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        a = LI()

        t = [a[0]]
        for c in a[1:]:
            b = t[-1]
            if b <= c:
                t.append(c)
                continue
            tt = b - c
            k = ((b+c) ** 2 - tt**2) ** 0.5
            if k > b:
                t.append(c)
        a = t[::-1]
        t = [a[0]]
        for c in a[1:]:
            b = t[-1]
            if b <= c:
                t.append(c)
                continue
            tt = b - c
            k = ((b+c) ** 2 - tt**2) ** 0.5
            if k > b:
                t.append(c)
        a = t[::-1]

        l = len(a)
        if l == 1:
            rr.append(a[0]*2)
            break
        r = a[0] + a[-1]
        for i in range(l-1):
            b = a[i]
            c = a[i+1]
            if b == c:
                r += b + c
                continue
            t = abs(b-c)
            r += ((b+c) ** 2 - t**2) ** 0.5

        rr.append('{:00.9f}'.format(r))
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        a = LI()

        l = len(a)
        if l == 1:
            rr.append(a[0]*2)
            break
        r = a[0] * 2
        p = [a[0]]
        for i in range(1,n):
            c = a[i]
            cp = c
            for j in range(i):
                b = a[j]
                bp = p[j]
                t = abs(b-c)
                u = ((b+c)**2 - t**2) ** 0.5
                tp = bp + u
                if cp < tp:
                    cp = tp
            p.append(cp)
            if r < cp + c:
                r = cp + c

        rr.append('{:00.9f}'.format(r))
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    c = [int(i) for i in input().split()]

    if N == 1:
        return c[0] *2
    r = c[0]*2
    x = [c[0]]
    for i in range(1,N):
        r_ = c[i]
        r_n = r_
        for j in range(i):
            b = c[j]
            x_= x[j]

            dt = 2 * ((r_*b)**(1/2))
            x_ += dt
            r_n = max(r_n,x_)
        x.append(r_n)
        if r < r_n + r_:
            r = r_n +r_
    #print(x)
    return r
    
print(solve())