Problem:


パティシエ

 ケーキ屋さんが、まちまちな大きさのロールケーキをたくさん作りました。あなたは、このケーキを箱に並べる仕事を任されました。

ロールケーキはとてもやわらかいので、他のロールケーキが上に乗るとつぶれてしまいます。ですから、図(a) のように全てのロールケーキは必ず箱の底面に接しているように並べなければなりません。並べ替えると必要な幅も変わります。

図(a)

図(b)

n 個のロールケーキの半径 r1, r2, ...,  rn と箱の長さを読み込み、それぞれについて、箱の中にうまく収まるかどうか判定し、並べる順番を工夫すると箱に入る場合は "OK"、どう並べても入らない場合には "NA"を出力するプログラムを作成してください。

ロールケーキの断面は円であり、箱の壁の高さは十分に高いものとします。 ただし、ロールケーキの半径は 3 以上 10 以下の整数とします。つまり、ケーキの半径に極端な差はなく、図(b) のように大きなケーキの間に小さなケーキがはまり込んでしまうことはありません。

Input

入力は複数のデータセットからなります。各データセットは以下の形式で与えられます。

W r1 r2 ... rn

最初に箱の長さを表す整数 W (1 ≤ W ≤ 1,000) が与えられます。 続いて、空白区切りで各ロールケーキの半径を表す整数 ri (3 ≤ ri ≤ 10) が与えられます。ケーキの個数 n は 12 以下です。

データセットの数は 50 を超えません。

Output

データセットごとに OK または NA を１行に出力してください。

Sample Input

30 4 5 6
30 5 5 5
50 3 3 3 10 10
49 3 3 3 10 10

Output for the Sample Input

OK
OK
OK
NA



Sample input:
30 4 5 6
30 5 5 5
50 3 3 3 10 10
49 3 3 3 10 10


Sample output:
OK
OK
OK
NA

Submission status: Wrong Answer

Solution code:
from collections import deque

def calcwidth(cks):
    if len(cks) == 1: return cks[0]*2
    width = cks[0] + cks[-1]
    for ck1,ck2 in zip(cks[:-1],cks[1:]):
        width += ((ck1+ck2)**2-(ck1-ck2)**2)**0.5
    return width

while True:
    try: W, *rs = list(map(float,input().split()))
    except: break
    rs = deque(sorted(rs))
    dp = [float('inf')]*len(rs)
    cs = deque([rs.popleft()])

    last_pick_small = -1
    # if -1: last pick up is smallest, if 0: last pick up is biggest
    while rs:
        if last_pick_small: nxt = rs.pop()
        else: nxt = rs.popleft()
        if abs(nxt-cs[0]) > abs(nxt-cs[-1]): cs.appendleft(nxt)
        else: cs.append(nxt)
        last_pick_small = -1-last_pick_small
    ret = calcwidth(list(cs))
    if ret < W: print('OK')
    else: print('NA')

Submission status: Wrong Answer

Solution code:
import sys
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0];
  a=a[1:]
  n=len(a)+1
  b=a[:]
  b[0::2]=a[:n/2]
  b[1::2]=a[n/2:]
  n-=1
  s=b[0]+b[n-1]
  for i in range(n-1): s+=2*(b[i]*b[i+1])**.5
  print ["OK","NA"][s>w]

Submission status: Wrong Answer

Solution code:
import sys
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0];
  a=sorted(a[1:])
  n=len(a)+1
  b=a[:]
  b[0::2]=a[:n/2]
  b[1::2]=a[n/2:]
  n-=1
  s=b[0]+b[n-1]
  for i in range(n-1): s+=2*(b[i]*b[i+1])**.5
  print ["OK","NA"][s>w]

Submission status: Wrong Answer

Solution code:
import sys
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0];
  a=sorted(a[1:])
  n=len(a)
  b=a[:]
  c=a[:]
  b[0::2]=a[n/2:][::-1]
  b[1::2]=a[:n/2]
  s1=b[0]+b[n-1]

  n+=1
  c[1::2]=a[n/2:][::-1]
  c[0::2]=a[:n/2]
  n-=1
  s2=c[0]+c[n-1]
  for i in range(n-1):
    s1+=2*(b[i]*b[i+1])**.5
    s2+=2*(c[i]*c[i+1])**.5
  s=min(s1,s2)
  print ["OK","NA"][s>w]

Submission status: Wrong Answer

Solution code:
import math

def shortest(chain,length,newr):
    if length-chain[0]+newr+2*math.sqrt(newr*chain[0])<length-chain[-1]+newr+2*math.sqrt(newr*chain[-1]):
        a=length-chain[0]+newr+2*math.sqrt(newr*chain[0])
        nc=[newr]+chain
    else:
        a=length-chain[-1]+newr+2*math.sqrt(newr*chain[-1])
        nc=chain+[newr]
    for i in range(1,len(chain)):
        newlength=length-2*math.sqrt(chain[i-1]*chain[i])+2*math.sqrt(chain[i-1]*newr)+2*math.sqrt(newr*chain[i])
        if newlength<a:
            a=newlength
            nc=chain[:i]+[newr]+chain[i:]
    return (a,nc)
    
while(1):
    try:
        din=[int(x) for x in raw_input().split()]
    except:
        break
    box=din[0]
    chain=[din[1]]
    length=2*din[1]
    if len(din)>2:
        for newr in din[2:]:
            (length,chain)=shortest(chain,length,newr)
    #print chain
    if box>=length:
        print 'OK'
    else:
        print 'NG'

Submission status: Wrong Answer

Solution code:
import math

def shortest(chain,length,newr):
    if length-chain[0]+newr+2*math.sqrt(newr*chain[0])<length-chain[-1]+newr+2*math.sqrt(newr*chain[-1]):
        a=length-chain[0]+newr+2*math.sqrt(newr*chain[0])
        nc=[newr]+chain
    else:
        a=length-chain[-1]+newr+2*math.sqrt(newr*chain[-1])
        nc=chain+[newr]
    for i in range(1,len(chain)):
        newlength=length-2*math.sqrt(chain[i-1]*chain[i])+2*math.sqrt(chain[i-1]*newr)+2*math.sqrt(newr*chain[i])
        if newlength<a:
            a=newlength
            nc=chain[:i]+[newr]+chain[i:]
    return (a,nc)
    
while(1):
    try:
        din=[int(x) for x in raw_input().split()]
    except:
        break
    box=din[0]
    chain=[din[1]]
    length=2*din[1]
    if len(din)>2:
        for newr in din[2:]:
            (length,chain)=shortest(chain,length,newr)
    #print chain
    if box>=length:
        print 'OK'
    else:
        print 'NA'

Submission status: Wrong Answer

Solution code:
from math import sqrt
en=map(int,raw_input().split())
w=en[0]
r=en[1:]
lr=len(r)

dp=[[float('inf')]*lr for _ in xrange(1<<lr)]
for i in xrange(lr):
    dp[1<<i][i]=r[i]
for i in xrange(1<<lr):
    for j in xrange(lr):
        if i>>j&1:
            for k in xrange(len(dp[i^(1<<j)])):
                dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+2*sqrt(r[k]*r[j]))

ans=float('inf')
for i in xrange(lr):
    ans=min(ans,dp[(1<<lr)-1][i]+r[i])
if ans<=w:
    print('OK')
else:
    print('NA')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

for s in sys.stdin:
    lst = list(map(int, s.split()))
    W = lst[0]
    R = lst[1:]
    R.sort()

    # zigzag
    Z = []

    while R:
        r = R.pop(0)
        Z.append(r)

        if R:
            r = R.pop(-1)
            Z.append(r)

    #print('Z', Z)

    l = 0
    n = len(Z)
    for i in range(0, n-1):
        r0 = Z[i]
        r1 = Z[i+1]

        x_length = math.sqrt((r0+r1)**2 - (r0-r1) ** 2)
        l += x_length

    l += Z[0]
    l += Z[-1]

    #print(l)
    if l <= W:
        print('OK')
    else:
        print('NA')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

for s in sys.stdin:
    lst = list(map(int, s.split()))
    W = lst[0]
    R = lst[1:]
    R.sort()
    n = len(R)

    # zigzag
    Z = [None] * n
    i = 0
    j = n - 1

    while R:
        # smalest append
        if R:
            r = R.pop(0)
            Z[i] = r
            i += 1
        if R:
            r = R.pop(0)
            Z[j] = r
            j -= 1

        # biggest append
        if R:
            r = R.pop(-1)
            Z[i] = r
            i += 1
        if R:
            r = R.pop(-1)
            Z[j] = r
            j -= 1

    #print('Z', Z)

    l = 0
    for i in range(0, n-1):
        r0 = Z[i]
        r1 = Z[i+1]

        x_length = math.sqrt((r0+r1)**2 - (r0-r1) ** 2)
        l += x_length

    l += Z[0]
    l += Z[-1]

    #print(l)
    if l <= W:
        print('OK')
    else:
        print('NA')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

def pythagoras(a, b):
    return 2 * math.sqrt(a * b)

for s in sys.stdin:
    lst = list(map(int, s.split()))
    W = lst[0]
    R = lst[1:]
    R.sort()
    n = len(R)
    
    if n == 0:
        print('OK')
        exit()
        
    if n == 1:
        if W >= R[0]:
            print('OK')
            exit()
        else:
            print('NA')
            exit()

    left = []
    right = []

    left.append(R.pop(0))
    right.append(R.pop(0))

    l = left[0] + right[0]
    while R:
        min_R = R[0]
        max_R = R[-1]

        left_R = left[-1]
        right_R = right[-1]

        if left_R <= right_R:
            if right_R - min_R >= max_R - left_R:
                right.append(R.pop(0))
                l += pythagoras(right_R, min_R)
            else:
                left.append(R.pop(-1))
                l += pythagoras(max_R, left_R)
        else:
            if left_R - min_R >= max_R - right_R:
                left.append(R.pop(0))
                l += pythagoras(left_R, min_R)
            else:
                right.append(R.pop(-1))
                l += pythagoras(max_R, right_R)

    l += pythagoras(left[-1], right[-1])

    if l <= W:
        print('OK')
    else:
        print('NA')

Submission status: Wrong Answer

Solution code:
import math
while 1:
    try:
        A=map(int, raw_input().split())
        W=A[0]
        B=[sorted(A[1:]), sorted(A[1:],reverse=1)]
        a=[[],[]]
        dr=1
        N=len(A[1:])
        k=0
        for j in range(N):
            i=j/2
            a[0].append(B[k][i])
            a[1].append(B[not k][i])
            k= not k
        ans=99999999999999999999
        for aa in a:
            b=aa[0]+aa[-1]
            for i in range(1,N):
                b += 2*math.sqrt(aa[i]*aa[i-1])
            ans=min(ans,b)
        if ans<=W:
            print 'OK'
        else:
            print 'NA'
    except:
        break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120

"""
import sys
from sys import stdin
input = stdin.readline


def calc_width(cakes):
    # ??±????????????????????????(?????????????????????????????????????????????????¨??????????)
    if len(cakes) == 1:
        return cakes[0]*2

    prev_r = cakes[0]
    width = prev_r

    for r in cakes[1:]:
        h_diff = abs(prev_r - r)
        if h_diff == 0:
            width += prev_r
            width += r
        else:
            w = ((prev_r + r)**2 - h_diff**2)**0.5
            width += w
        prev_r = r
    width += cakes[-1]

    return width


def main(args):
    for line in sys.stdin:
        data = [int(x) for x in line.split()]
        box_size = data[0]
        temp = data[1:]
        temp.sort()
        cakes = []

        head = True
        while temp:
            if head:
                cakes.append(temp[0])
                temp = temp[1:]
                head = False
            else:
                cakes.append(temp[-1])
                temp = temp[:-1]
                head = True
        result = calc_width(cakes)
        if result <= box_size:
            print('OK')
        else:
            print('NA')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120

"""
import sys
from sys import stdin
input = stdin.readline


def calc_width(cakes):
    # ??±????????????????????????(?????????)????????????????????????????????????????¨??????????
    if len(cakes) == 1:
        return cakes[0]*2

    prev_r = cakes[0]
    width = prev_r

    for r in cakes[1:]:
        h_diff = abs(prev_r - r)
        if h_diff == 0:
            width += prev_r
            width += r
        else:
            w = ((prev_r + r)**2 - h_diff**2)**0.5
            width += w
        prev_r = r
    width += cakes[-1]

    return width


def main(args):
    for line in sys.stdin:
        data = [int(x) for x in line.strip().split()]
        box_size = data[0]
        temp = data[1:]
        temp.sort()
        cakes = []

        head = True
        while temp:
            if head:
                cakes.append(temp[0])
                temp = temp[1:]
                head = False
            else:
                cakes.append(temp[-1])
                temp = temp[:-1]
                head = True
        result = calc_width(cakes)
        if result <= box_size:
            print('OK')
        else:
            temp = data[1:]
            temp.sort(reverse=True)
            cakes = []

            head = True
            while temp:
                if head:
                    cakes.append(temp[0])
                    temp = temp[1:]
                    head = False
                else:
                    cakes.append(temp[-1])
                    temp = temp[:-1]
                    head = True
            result = calc_width(cakes)
            if result <= box_size:
                print('OK')
            else:
                print('NA')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def mix(seq,start,end):
    seq.sort()
    q = [seq.pop(len(seq)/2)]
    while seq != []:
        cur = q[-1]
        if (abs(seq[0]-cur) > abs(seq[-1]-cur)):
            q.append(seq.pop(0))
        else:
            q.append(seq.pop())
    return [start]+q+[end]

def get_height(seq):
    return sum(abs(a-b) for a,b in zip(seq,seq[1:]))

while True:
    try:
        inputs = map(int,raw_input().split())
    except:
        break
    seq = inputs[1:]
    adj = inputs[0]
    hyp = sum(seq)*2
    n = len(seq)
    if n <= 2:
        print "OK" if hyp < adj else "NA"
        continue
    for a,b in combinations(xrange(n),2):
        opp = get_height(mix(seq[:a]+seq[a+1:b]+seq[b+1:],seq[a],seq[b]))
        if (hyp-(seq[a]+seq[b]))**2 - (adj-(seq[a]+seq[b]))**2 <= opp**2:
            print "OK"
            break
    else:
        print "NA"

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def mix(seq,start,end):
    seq.sort()
    q = [seq.pop(len(seq)/2)]
    while seq != []:
        cur = q[-1]
        if (abs(seq[0]-cur) > abs(seq[-1]-cur)):
            q.append(seq.pop(0))
        else:
            q.append(seq.pop())
    return [start]+q+[end]

def get_height(seq):
    #print "seq",seq
    #print "sum",sum(abs(a-b) for a,b in zip(seq,seq[1:]))
    return sum(abs(a-b) for a,b in zip(seq,seq[1:]))

while True:
    try:
        inputs = map(int,raw_input().split())
    except:
        break
    seq = inputs[1:]
    adj = inputs[0]
    hyp = sum(seq)*2
    n = len(seq)
    if n <= 2:
        print "OK" if hyp <= adj else "NA"
        continue
    for a,b in combinations(xrange(n),2):
        opp = get_height(mix(seq[:a]+seq[a+1:b]+seq[b+1:],seq[a],seq[b]))
        #print "hyp,adj,opp",(hyp-(seq[a]+seq[b]))**2,(adj-(seq[a]+seq[b]))**2,opp**2
        if (hyp-(seq[a]+seq[b]))**2 - (adj-(seq[a]+seq[b]))**2 <= opp**2:
            print "OK"
            break
    else:
        print "NA"

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def mix(seq,start,end):
    if seq == []:
        return [start,end]
    seq.sort()
    q = [seq.pop(len(seq)/2)]
    while seq != []:
        cur = q[-1]
        if (abs(seq[0]-cur) > abs(seq[-1]-cur)):
            q.append(seq.pop(0))
        else:
            q.append(seq.pop())
    return [start]+q+[end]

def get_height(seq):
    #print "seq",seq
    #print "sum",sum(abs(a-b) for a,b in zip(seq,seq[1:]))
    return sum(abs(a-b) for a,b in zip(seq,seq[1:]))

while True:
    try:
        inputs = map(int,raw_input().split())
    except:
        break
    seq = inputs[1:]
    adj = inputs[0]
    hyp = sum(seq)*2
    n = len(seq)
    if n == 1:
        print "OK" if hyp <= adj else "NA"
        continue        
    for a,b in combinations(xrange(n),2):
        opp = get_height(mix(seq[:a]+seq[a+1:b]+seq[b+1:],seq[a],seq[b]))
        #print "hyp,adj,opp",(hyp-(seq[a]+seq[b]))**2,(adj-(seq[a]+seq[b]))**2,opp**2
        if (hyp-(seq[a]+seq[b]))**2 - (adj-(seq[a]+seq[b]))**2 <= opp**2:
            print "OK"
            break
    else:
        print "NA"

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def mix(seq,start,end):
    if seq == []:
        return [start,end]
    q = [seq.pop(len(seq)/2)]
    while seq != []:
        cur = q[-1]
        if (abs(seq[0]-cur) > abs(seq[-1]-cur)):
            q.append(seq.pop(0))
        else:
            q.append(seq.pop())
    return [start]+q+[end]

def get_height(seq):
    #print "seq",seq
    #print "sum",sum(abs(a-b) for a,b in zip(seq,seq[1:]))
    return sum(abs(a-b) for a,b in zip(seq,seq[1:]))

while True:
    try:
        inputs = map(int,raw_input().split())
    except:
        break
    #print inputs
    seq = sorted(inputs[1:])
    adj = inputs[0]
    hyp = sum(seq)*2
    n = len(seq)
    if n == 0:
        print "OK"
        continue
    if n == 1:
        print "OK" if hyp <= adj else "NA"
        continue        

    for a,b in combinations(xrange(n),2):
        opp = get_height(mix(seq[:a]+seq[a+1:b]+seq[b+1:],seq[a],seq[b]))
        #print "hyp,adj,opp",(hyp-(seq[a]+seq[b]))**2,(adj-(seq[a]+seq[b]))**2,opp**2
        if (hyp-(seq[a]+seq[b]))**2 - (adj-(seq[a]+seq[b]))**2 <= opp**2:
            print "OK"
            break
    else:
        print "NA"

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def shuffle(seq,start,end):
    if seq == [] or len(seq) == 1:
        return seq
    a = sorted(range(3,11),key=lambda a:abs(6-a),reverse=True)
    #print "init", seq
    ret = []
    n = len(seq)

    while seq != []:
        for i in a:
            if i in seq:
                ret.append(seq.pop(seq.index(i)))
    
    #print "mid",ret
    cursor = n-1;
    while cursor != 0:
        #print ret
        if ret[cursor-1] == ret[cursor]:
            tmp = ret[cursor]
            for j in xrange(cursor-1,-1,-1):
                if tmp != ret[j-1]:
                    tmp = ret.pop(cursor)
                    ret.insert(j-1,tmp)
                    cursor += 1
                    break        
        cursor -= 1
    return [start] + ret + [end]


def get_height(seq):
    #print "seq",seq
    #print "sum",sum(abs(a-b) for a,b in zip(seq,seq[1:]))
    return sum(abs(a-b) for a,b in zip(seq,seq[1:]))


while True:
    try:
        inputs = map(int,raw_input().split())
    except:
        break
    #print "inputs:",inputs
    seq = sorted(inputs[1:])
    adj = inputs[0]
    hyp = sum(seq)*2
    n = len(seq)
    if n == 0:
        print "OK"
        continue
    if n == 1:
        print "OK" if hyp <= adj else "NA"
        continue        

    for a,b in combinations(xrange(n),2):
        opp = get_height(shuffle(seq[:a]+seq[a+1:b]+seq[b+1:],seq[a],seq[b]))
        #print "hyp,adj,opp",(hyp-(seq[a]+seq[b]))**2,(adj-(seq[a]+seq[b]))**2,opp**2
        if (hyp-(seq[a]+seq[b]))**2 - (adj-(seq[a]+seq[b]))**2 <= opp**2:
            print "OK"
            break
    else:
        print "NA"

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		raw_cakes=sorted(map(int,raw_input().split()))[::-1]
		box=raw_cakes.pop(0)
		cakes=[raw_cakes.pop(-1)]
		while raw_cakes:
			if raw_cakes: cakes.append(raw_cakes.pop( 0))
			if raw_cakes: cakes.append(raw_cakes.pop(-1))
			
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			r=cakes[i]+cakes[i+1]
			cos=(1-(abs(cakes[i]-cakes[i+1])*1.0/r)**2)**0.5
			size+=r*cos
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[raw_cakes.pop(-1)]
		while raw_cakes:
			if raw_cakes: cakes.append(raw_cakes.pop( 0))
			if raw_cakes: cakes.append(raw_cakes.pop(-1))
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			r=cakes[i]+cakes[i+1]
			cos=(1-(abs(cakes[i]-cakes[i+1])*1.0/r)**2)**0.5
			size+=r*cos
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[raw_cakes.pop(-1)]
		while raw_cakes:
			if raw_cakes: cakes.append(raw_cakes.pop( 0))
			if raw_cakes: cakes.append(raw_cakes.pop(-1))
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			size+=L(cakes[i],cakes[i+1])
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[]
		while raw_cakes:
			if raw_cakes: cakes.append(raw_cakes.pop(-1))
			if raw_cakes: cakes.append(raw_cakes.pop( 0))
		cakes=cakes[:len(cakes)/2]+cakes[len(cakes)/2:][::-1]
		print cakes
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			size+=L(cakes[i],cakes[i+1])
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[]
		while raw_cakes:
			if raw_cakes: cakes.append(raw_cakes.pop(-1))
			if raw_cakes: cakes.append(raw_cakes.pop( 0))
		cakes=cakes[:len(cakes)/2]+cakes[len(cakes)/2:][::-1]
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			size+=L(cakes[i],cakes[i+1])
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[]
		while len(raw_cakes)>1:
			if len(raw_cakes)>1: cakes.append(raw_cakes.pop( 0))
			if len(raw_cakes)>1: cakes.append(raw_cakes.pop(-1))
		cakes.insert(0,raw_cakes.pop())
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			size+=L(cakes[i],cakes[i+1])
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		raw_cakes=map(int,raw_input().split())
		box=raw_cakes.pop(0)
		raw_cakes=sorted(raw_cakes)[::-1]
		cakes=[raw_cakes.pop(0)]
		while len(raw_cakes)>1:
			cos=[L(cakes[-1],i)/(cakes[-1]+i) for i in raw_cakes]
			cakes.append(raw_cakes.pop(cos.index(min(cos))))
		cakes.insert(0,raw_cakes.pop())
		size=cakes[0]+cakes[-1]
		for i in range(len(cakes)-1):
			size+=L(cakes[i],cakes[i+1])
		print "OK" if size<=box else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		Cakes=map(int,raw_input().split())
		size_max=Cakes.pop(0)
		size_min=121
		for j in range(len(Cakes)):
			size=0
			cakes=Cakes[:]
			cake1=size=cakes.pop(j)
			while cakes:
				cos=[L(cake1,i)/(cake1+i) for i in cakes]
				cake2=cakes.pop(cos.index(min(cos)))
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake2
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5

while 1:
	try:
		Cakes=map(int,raw_input().split())
		size_max=Cakes.pop(0)
		size_min=999
		for j in range(len(Cakes)):
			size=0
			cakes=Cakes[:]
			cake1=size=cakes.pop(j)
			while cakes:
				cos=[L(cake1,i)/(cake1+i) for i in cakes]
				cake2=cakes.pop(cos.index(min(cos)))
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake2
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
    return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5
 
while 1:
    try:
        Cakes=map(int,raw_input().split())
        size_max=Cakes.pop(0)
        size_min=999
        for j in range(len(Cakes)):
            cakes=Cakes[:]
            cake1=size=cakes.pop(j)
            while cakes:
                cos=[L(cake1,i)/(cake1+i) for i in cakes]
                cake2=cakes.pop(cos.index(min(cos)))
            	size+=L(cake1,cake2)
            	cake1=cake2
            size+=cake2
            size_min=min(size,size_min)
        print "OK" if size_min<=size_max else "NA"
    except:
        break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5
 
while 1:
	try:
		Cakes=map(int,raw_input().split())
		size_max=Cakes.pop(0)
		size_min=999
		for j in range(len(Cakes)):
			cakes=Cakes[:]
			cake1=size=cakes.pop(j)
			while cakes:
				cos=[L(cake1,i)/(cake1+i) for i in cakes]
				cake2=cakes.pop(cos.index(min(cos)))
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake2
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5
 
while 1:
	try:
		Cakes=map(int,raw_input().split())
		size_max=Cakes.pop(0)
		size_min=999
		for j in range(len(Cakes)):
			cakes=Cakes[:]
			size=cake1=cakes.pop(j)
			while cakes:
				cos=[L(cake1,i)/(cake1+i) for i in cakes]
				cake2=cakes.pop(cos.index(min(cos)))
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake2
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Wrong Answer

Solution code:
def L(cake1,cake2):
	return ((cake1+cake2)**2-abs(cake1-cake2)**2)**0.5
 
while 1:
	try:
		Cakes=map(int,raw_input().split())
		size_max=Cakes.pop(0)
		size_min=999
		for j in range(len(Cakes)):
			cakes=Cakes[:]
			cake1=cakes.pop(j)
			size=cake1
			while cakes:
				cos=[L(cake1,i)/(cake1+i) for i in cakes]
				cake2=cakes.pop(cos.index(min(cos)))
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake2
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Time Limit Exceeded

Solution code:
import sys,itertools
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0]
  n=len(a)-1
  A=itertools.permutations(a[1:],n)
  s0=1e9
  for e in A:
    s=e[0]+e[-1]
    for i in range(n-1): s+=2*(e[i]*e[i+1])**.5
    if s<s0: s0=s
    if s0<=w: break
  print ["OK","NA"][s0>w]

Submission status: Time Limit Exceeded

Solution code:
import Queue, math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) < l:
        print "OK"
    else:
        que = Queue.PriorityQueue()
        dp = [[1000.0 for i in xrange(n)] for j in xrange(2**n)]
        que.put((0.0, 0, -1))
        while not que.empty():
            co, state, last = que.get()
            if last!=-1 and dp[state][last] < co:
                continue
            for i in xrange(n):
                if (state & (1<<i))==0:
                    nxt = co + math.sqrt(r[last]*r[i])*2.0 if last!=-1 else r[i]
                    if nxt < dp[state | (1<<i)][i]:
                        dp[state | (1<<i)][i] = nxt
                        que.put((nxt, state | (1<<i), i))
        ans = 1000.0
        for i in xrange(n):
            ans = min(ans, dp[2**n-1][i]+r[i])
        print "OK" if ans < l+0.000000001 else "NA"

Submission status: Time Limit Exceeded

Solution code:
import Queue, math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) <= l:
        print "OK"
    else:
        n2 = 2**n-1
        que = Queue.PriorityQueue()
        dp = [[1000.0 for i in xrange(n)] for j in xrange(2**n)]
        que.put((0.0, 0, -1))
        ok = False
        while not ok and not que.empty():
            co, state, last = que.get()
            if last!=-1 and dp[state][last] < co:
                continue
            for i in xrange(n):
                if (state & (1<<i))==0:
                    nxt = co + math.sqrt(r[last]*r[i])*2.0 if last!=-1 else r[i]
                    nst = state | (1<<i)
                    if nxt + r[i] < l+0.000000001 and nxt < dp[nst][i]:
                        if nst==n2:
                            ok = True
                            break
                        dp[nst][i] = nxt
                        que.put((nxt, nst, i))
        print "OK" if ok else "NA"

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt


def rec(state, v):
    if state == (1 << N) - 1:
        return cakes[v]
    if dp[state][v] != -1:
        return dp[state][v]

    ret = INF
    for i in range(N):
        if not (state >> i & 1):
            ret = min(ret, rec(state | 1 << i, i) + sqrt(pow(cakes[i] + cakes[v], 2) - pow(cakes[i] - cakes[v], 2)))
    dp[state][v] = ret
    return ret


testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    ans = INF
    for i in range(N):
        dp = [[-1] * N for _ in range(1 << N)]
        ans = min(ans, rec(1 << i, i) + cakes[i])
    print('OK' if ans <= box else 'NA')

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt

testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[(1 << N) - 1][0] = 0
    for state in reversed(range(1 << N)):
        for v in range(N):
            for u in range(N):
                if not (state >> u & 1):
                    dp[state][v] = min(dp[state][v], dp[state | 1 << u][u] + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    print(*dp[0])
    print('OK' if min(dp[0]) <= box else 'NA')

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt

testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[(1 << N) - 1][0] = 0
    for state in reversed(range(1 << N)):
        for v in range(N):
            if not dp[state][v]:
                continue
            for u in range(N):
                if not (state >> u & 1):
                    dp[state][v] = min(dp[state][v], dp[state | 1 << u][u] + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    print('OK' if min(dp[0]) <= box else 'NA')

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations

def get_dist(item):
    ans = 0
    for i in range(len(item) - 1):
        r1, r2 = item[i], item[i+1]
        x = math.sqrt(pow(r1+r2, 2) - pow(r1-r2,2))
        ans += x
    ans += item[0] + item[-1]
    return ans

while True:
    try:
        tmp = map(int, raw_input().split())
    except EOFError:
        break
    length = tmp[0]
    rs = tmp[1:]
    for item in permutations(rs):
        if get_dist(item) <= length:
            print 'OK'
            break
    else:
        print 'NA'

Submission status: Accepted

Solution code:
INF = 10 ** 20
def get_dist(r1, r2):
  c = r1 + r2
  b = abs(r1 - r2)
  return (c ** 2 - b ** 2) ** (1 / 2)

def minimum_width(rest, r, dic):
  if (rest, r) in dic:
    return dic[(rest, r)]
  if rest == ():
    return r

  ret = INF
  lenr = len(rest)
  for i, c in enumerate(rest):
    ret = min(ret, minimum_width(tuple(rest[j] for j in range(lenr) if i != j), rest[i], dic) + get_dist(r, rest[i]))
  dic[(rest, r)] = ret
  return ret


while True:
  try:
    lst = list(map(int, input().split()))
    w = lst[0]
    cakes = lst[1:]
    cakes.sort()
    lenc = len(cakes)
    dic = {}
    ans = INF
    for i in range(lenc):
      ans = min(ans, minimum_width(tuple(cakes[j] for j in range(lenc) if i != j), cakes[i], dic) + cakes[i])
    if w >= ans:
      print("OK")
    else:
      print("NA")
  except EOFError:
    break