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: Accepted

Solution code:
INF = 10 ** 20
def get_dist(r1, r2):
  return ((r1 + r2) ** 2 - (r1 - r2) ** 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 c in rest:
    next_rest = list(rest)
    next_rest.remove(c)
    ret = min(ret, minimum_width(tuple(next_rest), c, dic) + get_dist(r, c))
  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

Submission status: Accepted

Solution code:
INF = 10 ** 20

def get_dist(r1, r2):
  return ((r1 + r2) ** 2 - (r1 - r2) ** 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 c in rest:
    next_rest = list(rest)
    next_rest.remove(c)
    ret = min(ret, minimum_width(tuple(next_rest), c, dic) + get_dist(r, c))
  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 c in cakes:
      tmp = cakes[:]
      tmp.remove(c)
      ans = min(ans, minimum_width(tuple(tmp), c, dic) + c)
    if w >= ans:
      print("OK")
    else:
      print("NA")
  except EOFError:
    break

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0]
  a=sorted(a[1:])
  A=[]
  try:
    while a:
      A+=[a.pop(0)]
      A=[a.pop()]+A
      A+=[a.pop()]
      A=[a.pop(0)]+A
  except: pass
  a=A[0]+A[-1]
  for i in range(len(A)-1): a+=2*(A[i]*A[i+1])**.5
  print ["OK","NA"][a>w]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import 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:
        s = []
        if n>1:
            r.sort()
            for i in xrange(n/2):
                s = [r[i]] + s[::-1] + [r[-i-1]]
            if n&1:
                if abs(s[0]-r[n/2]) < abs(s[-1]-r[n/2]):
                    s.append(r[n/2])
                else:
                    s = [r[n/2]] + s
        else:
            s = r
        ans = s[0] + s[-1]
        for i in xrange(n-1):
            ans += 2*math.sqrt(s[i]*s[i+1])
        print "OK" if ans < 0.000000001+l else "NA"

Submission status: Accepted

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 state == 0:
            ret = min(ret, rec(1 << i, i) + cakes[i])
        elif 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
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')

Submission status: Accepted

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 u in range(N):
        if state == 0:
            ret = min(ret, rec(1 << u, u) + cakes[u])
        elif not (state >> u & 1):
            ret = min(ret, rec(state | 1 << u, u) + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - 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
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')

Submission status: Accepted

Solution code:
from math import sqrt
while 1:
    try:
        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')
    except:break

Submission status: Accepted

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()

        min_width = float('inf')
        cake = []
        if len(temp) < 3:
            cakes = temp[:]
        elif len(temp) == 3:
            cakes = [temp[1], temp[2], temp[0]]
        else:
            cakes = [temp[1] ,temp[-1], temp[0]]
            temp = temp[2:-1]
            tail = True
            small = False
            while temp:
                if tail:
                    if small:
                        cakes.append(temp[0])
                        temp = temp[1:]
                        tail = False
                    else:
                        cakes.append(temp[-1])
                        temp = temp[:-1]
                        tail = False
                else:
                    if small:
                        cakes.insert(0, temp[0])
                        temp = temp[1:]
                        small = False
                        tail = True
                    else:
                        cakes.insert(0, temp[-1])
                        temp = temp[:-1]
                        small = True
                        tail = True

        result = calc_width(cakes)
        min_width = min(result, min_width)

        temp = data[1:]
        temp.sort()
        cake = []
        if len(temp) < 3:
            cakes = temp[:]
        elif len(temp) == 3:
            cakes = [temp[1], temp[0], temp[2]]
        else:
            cakes = [temp[-2] ,temp[0], temp[-1]]
            temp = temp[1:-2]
            tail = True
            small = True
            while temp:
                if tail:
                    if small:
                        cakes.append(temp[0])
                        temp = temp[1:]
                        tail = False
                    else:
                        cakes.append(temp[-1])
                        temp = temp[:-1]
                        tail = False
                else:
                    if small:
                        cakes.insert(0, temp[0])
                        temp = temp[1:]
                        small = False
                        tail = True
                    else:
                        cakes.insert(0, temp[-1])
                        temp = temp[:-1]
                        small = True
                        tail = True
        result = calc_width(cakes)
        min_width = min(result, min_width)



        if min_width <= box_size:
            print('OK')
        else:
            print('NA')


from itertools import permutations
def main2(args):
    data = [3, 3, 3, 10, 10]

    p = permutations(data, len(data))


    best_fit = float('inf')
    for cakes in p:
        result = calc_width(cakes)
        if result < best_fit:
            best_fit = result
            print(cakes)
            print(result)


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

Submission status: Accepted

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)
        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()

        # ??±??????????????????????????????????????????????????????????????????????????????
        min_width = float('inf')

        cakes = [temp[0]]
        temp = temp[1:]
        pick_large = True
        while temp:
            if pick_large:
                pick = temp[-1]
                temp = temp[:-1]
                pick_large = False
                diff_front = abs(pick - cakes[0])
                diff_rear = abs(pick - cakes[-1])
                if diff_front > diff_rear:
                    cakes.insert(0, pick)
                else:
                    cakes.append(pick)
            else:
                pick = temp[0]
                temp = temp[1:]
                pick_large = True
                diff_front = abs(pick - cakes[0])
                diff_rear = abs(pick - cakes[-1])
                if diff_front > diff_rear:
                    cakes.insert(0, pick)
                else:
                    cakes.append(pick)

        result = calc_width(cakes)
        min_width = min(result, min_width)

        if min_width <= box_size:
            print('OK')
        else:
            print('NA')


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

Submission status: Accepted

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)
        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 = [temp[0]]
        temp = temp[1:]
        pick_large = True
        pick = 0
        while temp:
            if pick_large:
                pick = temp[-1]
                temp = temp[:-1]
                pick_large = False
            else:
                pick = temp[0]
                temp = temp[1:]
                pick_large = True

            diff_front = abs(pick - cakes[0])
            diff_rear = abs(pick - cakes[-1])
            if diff_front > diff_rear:
                cakes.insert(0, pick)
            else:
                cakes.append(pick)

        # ??±????????¨???????¨????????¨????????????±?????\???????¢??????????
        result = calc_width(cakes)
        if result <= box_size:
            print('OK')
        else:
            print('NA')


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

Submission status: Accepted

Solution code:
# AOJ 0120 Patisserie
# Python3 2018.6.23 bal4u

INF = 0x7fffffff
R = 100000
d = [[0 for j in range(13)] for i in range(13)]  # ロールケーキ円心間の水平距離
for i in range(3, 11):
	ii = i*i
	for j in range(i, 11):
		d[i][j] = d[j][i] = int(2*R * ii**0.5)
		ii += i

while 1:
	try: r = list(map(int, input().split()))
	except: break
	W = r.pop(0)
	if 2*sum(r) <= W:
		print("OK")
		continue
	n = len(r)
	W *= R
	dp = [[INF for j in range(1<<n)] for i in range(n)]
	for i in range(n): dp[i][1<<i] = r[i]*R
	lim = 1<<n
	for k in range(lim):
		for i in range(n):
			if k & (1<<i): continue
			for j in range(n):
				dp[i][k|(1<<i)] = min(dp[i][k|(1<<i)], dp[j][k] + d[r[i]][r[j]])
	w = 240*R
	for i in range(n):
		dp[i][lim-1] += r[i]*R
		if dp[i][lim-1] < w: w = dp[i][lim-1];
	print("OK" if w <= W else "NA")

Submission status: Accepted

Solution code:
def f(rad1, rad2):
    return float((rad1 + rad2) ** 2 - abs(rad1 - rad2) ** 2) ** 0.5

while True:
    try:
        data = map(int, raw_input().split())
    except:
        break
    lim, rad, n = data[0], data[1:], len(data) - 1
    dp = [[0] * (1 << n) for _ in xrange(n)]
    for r in xrange(n):
        dp[r][1 << r] = rad[r]
    for b in xrange(1, 1 << n):
        for r in xrange(n):
            if b & (1 << r) == 0:
                dp[r][b + (1 << r)] = min(f(rad[rr], rad[r]) + dp[rr][b]
                                            for rr in xrange(n) if ((1 << rr) & b) != 0)
    print "OK" if lim >=  min(dp[r][(1 << n) - 1] + rad[r] for r in xrange(n)) else "NA"

Submission status: Accepted

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]
		size_min=999
		for j in range(len(Raw_cakes)):
			size=0
			raw_cakes=Raw_cakes[:]
			cakes=[raw_cakes.pop(j)]
			while raw_cakes:
				cos=[L(cakes[-1],i)/(cakes[-1]+i) for i in raw_cakes]
				cakes.append(raw_cakes.pop(cos.index(min(cos))))
			size=cakes[0]+cakes[-1]
			for i in range(len(cakes)-1):
				size+=L(cakes[i],cakes[i+1])
			size_min=min(size,size_min)
		print "OK" if size_min<=box else "NA"
	except:
		break

Submission status: Accepted

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)
        Cakes=sorted(Cakes)[::-1]
        size_min=999
        for j in range(len(Cakes)):
            cakes=Cakes[:]
            box=[cakes.pop(j)]
            while cakes:
                cos=[L(box[-1],i)/(box[-1]+i) for i in cakes]
                box.append(cakes.pop(cos.index(min(cos))))
            size=box[0]+box[-1]
            for i in range(len(box)-1):
                size+=L(box[i],box[i+1])
            size_min=min(size,size_min)
        print "OK" if size_min<=size_max else "NA"
    except:
        break

Submission status: Accepted

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[:]
			box=[cakes.pop(j)]
			while cakes:
			    cos=[L(box[-1],i)/(box[-1]+i) for i in cakes]
			    box.append(cakes.pop(cos.index(min(cos))))
			size=box[0]+box[-1]
			for i in range(len(box)-1):
				size+=L(box[i],box[i+1])
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Accepted

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,idx=min([(L(cake1,cakes[i])/(cake1+cakes[i]),i) for i in range(len(cakes))])
				cake2=cakes.pop(idx)
				size+=L(cake1,cake2)
				cake1=cake2
			size+=cake1
			size_min=min(size,size_min)
		print "OK" if size_min<=size_max else "NA"
	except:
		break

Submission status: Accepted

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 u in range(N):
        if state == 0:
            ret = min(ret, rec(1 << u, u) + cakes[u])
        elif not (state >> u & 1):
            ret = min(ret, rec(state | 1 << u, u) + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - 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
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')

Submission status: Runtime Error

Solution code:
import math

def f1():
    total = []
    for i in range(len(c_l)-1):
        x2 = 0
        if (i+1) % 2 == 0:
            x2 = (c_l[i+1]+c_l[i])**2 - (c_l[i+1]-c_l[i])**2
        else:
            x2 = (c_l[i]+c_l[i+1])**2 - (c_l[i]-c_l[i+1])**2
        x = math.sqrt(x2)
        total.append(x)
    else:
        total.append(c_l[0])
        total.append(c_l[-1])
    return f3(total)
        
def f2():
    total = []
    for i in range(len(c_l)-1):
        x2 = 0
        if (i+1) % 2 == 0:
            x2 = (c_l[i]+c_l[i+1])**2 - (c_l[i]-c_l[i+1])**2
        else:
            x2 = (c_l[i+1]+c_l[i])**2 - (c_l[i+1]-c_l[i])**2
        x = math.sqrt(x2)
        total.append(x)
    else:
        total.append(c_l[0])
        total.append(c_l[-1])
    return f3(total)
        
def f3(total):
    if sum(total) <= l:
        return True
    else:
        return False

while True:
    try:
        line = map(int, raw_input().split())
        l = line[0]
        lis = sorted(line[1:])
        c_lis = lis[:]
        c_l = []
        if len(lis) % 2 == 0:
            while True:
                c_l.append(lis[-1])
                c_l.append(lis[0])
                del lis[-1]
                del lis[0]
                if len(lis) == 0:
                    break
            if f1():
                print 'OK'
            else:
                print 'NA'
        else:
            while True:
                c_l.append(lis[-1])
                c_l.append(lis[0])
                del lis[-1]
                del lis[0]
                if len(lis) == 1:
                    c_l.append(lis[0])
                    break
            if f1():
                print 'OK'
            else:
                c_l = []
                while True:
                    c_l.append(c_lis[0])
                    c_l.append(c_lis[-1])
                    del c_lis[0]
                    del c_lis[-1]
                    if len(c_lis) == 1:
                        c_l.append(c_lis[0])
                        break
                if f2():
                    print 'OK'
                else:
                    print 'NA'
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
import math

def f1():
    total = []
    for i in range(len(c_l)-1):
        x2 = 0
        if (i+1) % 2 == 0:
            x2 = (c_l[i+1]+c_l[i])**2 - (c_l[i+1]-c_l[i])**2
        else:
            x2 = (c_l[i]+c_l[i+1])**2 - (c_l[i]-c_l[i+1])**2
        x = math.sqrt(x2)
        total.append(x)
    else:
        total.append(c_l[0])
        total.append(c_l[-1])
    return f3(total)
        
def f2():
    total = []
    for i in range(len(c_l)-1):
        x2 = 0
        if (i+1) % 2 == 0:
            x2 = (c_l[i]+c_l[i+1])**2 - (c_l[i]-c_l[i+1])**2
        else:
            x2 = (c_l[i+1]+c_l[i])**2 - (c_l[i+1]-c_l[i])**2
        x = math.sqrt(x2)
        total.append(x)
    else:
        total.append(c_l[0])
        total.append(c_l[-1])
    return f3(total)
        
def f3(total):
    if sum(total) <= l:
        return True
    else:
        return False

while True:
    try:
        line = map(int, raw_input().split())
        l = line[0]
        lis = sorted(line[1:])
        c_lis = lis[:]
        if len(lis) % 2 == 0:
            c_l = []
            while True:
                c_l.append(lis[-1])
                c_l.append(lis[0])
                del lis[-1]
                del lis[0]
                if len(lis) == 0:
                    break
            if f1():
                print 'OK'
            else:
                print 'NA'
        else:
            c_l = []
            while True:
                c_l.append(lis[-1])
                c_l.append(lis[0])
                del lis[-1]
                del lis[0]
                if len(lis) == 1:
                    c_l.append(lis[0])
                    break
            if f1():
                print 'OK'
            else:
                c_l = []
                while True:
                    c_l.append(c_lis[0])
                    c_l.append(c_lis[-1])
                    del c_lis[0]
                    del c_lis[-1]
                    if len(c_lis) == 1:
                        c_l.append(c_lis[0])
                        break
                if f2():
                    print 'OK'
                else:
                    print 'NA'
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
import 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:
        r.sort()
        s = []
        for i in xrange(n/2):
            s = [r[i]] + s[::-1] + [r[-i-1]]
        if n&1:
            if abs(s[0]-r[n/2]) < abs(s[-1]-r[n/2]):
                s.append(r[n/2])
            else:
                s = [r[n/2]] + s
        ans = s[0] + s[-1]
        for i in xrange(n-1):
            ans += 2*math.sqrt(s[i]*s[i+1])
        print "OK" if ans < 0.000000001+l else "NA"

Submission status: Runtime Error

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)

    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')