<repo_name>thegriglat/acm.timus.ru<file_sep>/unsolved/1153.py
#!/usr/bin/python
N = input()
<file_sep>/unsolved/1306.py
#!/usr/bin/python

import sys

def getMediana(A,sorted=False):
    if not sorted:
        A.sort()
    if len(A) % 2 != 0:
        return A[len(A) // 2]
    else:
        return 0.5 * (A[len(A)//2 - 1] + A[len(A) // 2])

sys.stdin = open("1306.txt")

N = input()
n = []
for i in xrange(N):
    temp = input()
    n.append(temp)

print getMediana(n) if N < 100 else print 0<file_sep>/solved_2.6/1014.py
#!/usr/bin/python
def deliteli(N):
    d = {}
    for i in xrange(10):
        d[i] = 0
    if N == 0:
        return ([],True)
    for i in xrange(2, 10,1):
        while N % i == 0:
            d[i] += 1
            N = N / i
    if N == 1:
        return (d,True)
    else:
        return (d,False)
            
def getN(d):
    s = ""
    for i in d.iterkeys():
        for j in xrange(d[i]):
            s += str(i)
    if s != "":
        return s
    else:
        return 1

def SafePlus(key,value):
    global d
    if d.get(key) != None:
        d[key] += value
    else:
        d[key] = value
def RemZero():
    global d
    for i in xrange(10):
        if i in d.keys() and d[i] <= 0:
            del d[i]

def RemDupl():
    global d
    if d.get(2) >= 3:
        SafePlus(8,1)
        d[2] -= 3
    if d.get(3) >= 2:
        SafePlus(9,1)
        d[3] -= 2
    if d.get(4) >= 1 and d.get(2) >= 1:
        SafePlus(8,1)
        d[4] -= 1
        d[2] -= 1
    if d.get(2) >= 1 and d.get(3) >= 1:
        SafePlus(6,1)
        d[3] -= 1
        d[2] -= 1
    if d.get(2) >= 2:
        SafePlus(4,1)
        d[2] -= 2

N = int(raw_input().rstrip())
(d,stat) = deliteli(N)
ans = 10
if d != [] and stat == True : 
    oldd = None
    while oldd != d:
       oldd = d.copy()
       RemDupl()
    RemZero()
    ans = getN(d)
if N == 0:
    ans = 10 
if 1 <= N <= 9:
    ans = N
if stat == False:
    ans = -1
if ans == 0:
    ans = -1
print ans
<file_sep>/unsolved/1413.py
#!/ust/bin/python
import sys
sqr2 = 0.70710678118654757
def Goxy(num):
    global x, y,sqr2
    if num == 8:
        y += 1
    elif num == 2:
        y -= 1
    elif num == 6:
        x += 1
    elif num == 4:
        x -= 1
    elif num == 9:
        x += sqr2
        y += sqr2
    elif num == 7:
        x -= sqr2
        y += sqr2
    elif num == 3:
        x += sqr2
        y -= sqr2
    elif num == 1:
        x -= sqr2
        y -= sqr2

def Go(num,mode=None):
    global sqr2
    x = 0
    y = 0
    if num == 8:
        y += 1
    elif num == 2:
        y -= 1
    elif num == 6:
        x += 1
    elif num == 4:
        x -= 1
    elif num == 9:
        x += sqr2
        y += sqr2
    elif num == 7:
        x -= sqr2
        y += sqr2
    elif num == 3:
        x += sqr2
        y -= sqr2
    elif num == 1:
        x -= sqr2
        y -= sqr2
    elif num == 0:
        pass
    if mode == "x":
        return x
    elif mode == "y":
        return y

Mx = [[ Go(i,"x") + Go(j,"x") for j in xrange(0,10)] for i in xrange(0,10)]
My = [[ Go(i,"y") + Go(j,"y") for j in xrange(0,10)] for i in xrange(0,10)]
Mx[0] = [0] * len(Mx[0])
My[0] = [0] * len(My[0])
#sys.stdin = open("1413.txt")
s = sys.stdin.readline().rstrip()
x = 0
y = 0
i = 0
N = len(s)

while i < N:
    num = s[i:i+2]
    if len(num) == 1:
        Goxy(int(num))
        break
    istep,jstep = num
    istep = int(istep)
    jstep = int(jstep)
    x += Mx[istep][jstep]
    y += My[istep][jstep]
    i += 2
    if istep == 0 or jstep == 0 :
        break

print "%.10f %.10f" % (x,y)<file_sep>/unsolved/1002.py
#!/usr/bin/python

import sys,math,itertools,re
sys.stdin = open("1002.txt","r")
def getstdin(Type="str"):
    line = sys.stdin.readline().rstrip()
    if Type == "str":
        return line
    elif Type == "int":
        return int(line)
    elif Type == "float":
        return float(line)
    elif Type == "long":
        return long(line)

def getwords(n):
    global tel
    itn = iter(n)
    tell = []
    words = []
    for c in itn:
        tell.append(tel[int(c)])
    telcomb = itertools.product(*tell)
    for i in telcomb:
        s = ""
        for c in i:
            s += c
        words.append(s)
    return words

def getdata():
    n = getstdin("str")
    if n == "-1":sys.exit(0)
    words = getwords(n)
    dictN = getstdin("int")
    dct = []
    for i in xrange(dictN):
        dct.append(getstdin("str"))
    return (words,dct)

def splitword(word,dct):
    w = word
    tempd = dct
    s = "("
    for i in dct:
        s += i + "|"
    s = s[:-1]
    s += ")?"
    res = []
    s = s * len(dct)
    for d in dct:
        dct = tempd
        for w1 in w:
            if d not in w1: del dct[dct.index(d)]
        for i in re.findall(s,w1):
            result = []
            for j in i:
                if j != "": result.append(j)
            res.append(  str(result)[1:-1].replace(",","").replace("'",""))
    while "" in res: res.remove("")
    res = list(set(res))
    mini = 1000
    minit = ""
    for i in res:
        if len(i.split()) <= mini:
            mini = len(i.split())
            minit = i
    return minit

def resultword(words,dct):
    resultword = []
    for w in words:
        temp = w
        for d in dct:
            temp = temp.replace(d,"")
        if len(temp) == 0:
            resultword.append(w)
    return resultword

tel = [("o","q","z"),
    ("i","j"),
    ("a","b","c"),
    ("d","e","f"),
    ("g","h"),
    ("k","l"),
    ("m","n"),
    ("p","r","s"),
    ("t","u","v"),
    ("w","x","y")]

while True:
    (words,dct) = getdata()
    rword = resultword(words,dct)
    del words
    if len(rword) == 0:
        print "No solution."
    else:
        print splitword(rword,dct)

<file_sep>/solved_2.6/1794.py
#!/usr/bin/python
from sys import stdin
dict

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split(" ")]
mini = 1e10
b = [0 for i in xrange(len(a))]
for i in xrange(len(a)):
    j = i - a[i]  + 1
    if j < 0:
        j += len(a)
    b[j] += 1
print b.index(max(b)) + 1

<file_sep>/solved_2.6/1079.py
#!/usr/bin/python
import sys
def addai(key,value):
    global ai
    if key in ai.keys():
        return None
    else:
        ai[key] = value

def getai(n):
    global ai
    if n in ai.keys():
        return ai[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n % 2 == 0:
        i = int(n / 2)
        temp = getai(i)
        addai(n,temp)
        return temp
    else:
        i = n // 2 
        temp = getai(i) +getai(i+1)
        addai(n,temp)
        return temp

line = int(sys.stdin.readline().rstrip())
a = []
a.append(line)
while (line != 0):
     line = int(sys.stdin.readline().rstrip())
     a.append(line)
ai = {0:0,1:1}
a.pop(len(a) - 1)
for i in xrange(2,max(a) + 1):
    if i % 2 == 0:
        ai[i] = ai[int(i//2)]
    else:
        ai[i] = ai[int(i//2)] + ai[int(i//2)+1]

for test in a:
    maxi = 0
    for i in xrange(0,test + 1):
        t = ai[i]
        if t > maxi:
            maxi = t
    print maxi
<file_sep>/solved_2.6/1047.py
#!/usr/bin/python

import sys
            
def M2T():
    global B
    global N
    k = 0
    a = 2
    for i in xrange(N - 2,-1,-1):
        a = 2 + k
        k = -1 / (a + 0.0)
        B[i] -= k * B[i+1]
    k = -1 / (0.0 + a)
    if N != 1: a = 2 + k
    return  B[0] / (0.0 + a )
    
sys.stdin = open("1047.txt", "r")
N = int(sys.stdin.readline())
a0 = float(sys.stdin.readline())
an1 = float(sys.stdin.readline())
B = [float(sys.stdin.readline()) * (-2)   for x in xrange(0,N)]
B[0] += a0
B[N-1] += an1
print "%.2f" % (M2T())<file_sep>/solved_2.6/1005.py
#!/usr/bin/python
import sys

l1 = sys.stdin.readline()
del l1
line = sys.stdin.readline().rstrip()
a = line.split()
b = []
for i in a:
    b.append(int(i))

del a
b.sort()
sl = []
m1,m2 = 0,0
c = []
c += b 
m1 = b.pop(len(b) - 1)
while len(b) != 0:
    if m1 >= m2:
        m2 += b.pop(len(b) - 1)
    else:
        m1 += b.pop(len(b) - 1)

for i in xrange(len(c)):
    sl.append(abs(sum(c[i:]) - sum(c[:i])))

if abs(m2-m1) < min(sl):
    print abs(m2-m1)
else:
    print min(sl)
<file_sep>/unsolved/1297.py
#!/usr/bin/python
import sys

a = sys.stdin.readline().rstrip()
a = "ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA"
a = " " + a + " "
d = []
for i in xrange(len(a)):
    for j in xrange(len(a)):
        if a[i:j] == a[j-1:i-1:-1] and a[i:j] != "":
            d.append(a[i:j])
maxl = max(len(s) for s in d)
q = []
for i in d:
    if len(i) == maxl:
        q.append(i)
del d
idx = []
for i in q:
    idx.append(a.index(i))
print q[idx.index(min(idx))]<file_sep>/solved_2.6/1336.py
#!/usr/bin/python
#m**2 = k**3 * N


n = input()
print long(n **2 )
print long(n)
    <file_sep>/unsolved/1073.py
#!/usr/bin/python

import sys,math

def getL(n):
    """
    Decomposition of n by Lagrange theorem.
    n = a**2 + b**2 + c**2 + d**2
    """
    if int(math.sqrt(n)) ** 2 == N:
        return 1
    i = 0
    a = 5
    while a > 0:
        a = int(math.sqrt(n)) - i
        b = math.sqrt(n - a ** 2)
        if a < b: break     #Optimize 2x
        #print a, b
        if int(b) == b:
            return 2
        i += 1
    stop = int(math.sqrt(n)) + 1
    m = 0
    i = [0] * 3
    speed = 3
    if N < 81:
        speed = 1
    for i[0] in xrange(1,stop // speed):
        for i[1] in xrange(i[0],stop // speed):
            for i[2] in xrange(i[1],stop):
                #print i
                if sum([i[x] ** 2 for x in xrange(3)])  == n:
                    return 3
    return 4

N = input()
print getL(N)

<file_sep>/solved_2.6/1020.py
#!/usr/bin/python
import sys
import math
def getLine(p1,p2):
    (x1,y1) = p1
    (x2,y2) = p2
    if x2 - x1 != 0:
        k = (y2 - y1) / float(x2 - x1)
    else :
        k = 0
    b = y1 - k * x1
    return (k,b)

def getAddB(k, R):
    phi = math.atan(k)
    return R * math.cos(phi)
def getConnect(p1,R1,p2):
    (x,y) = p1
    addb = getAddB(getLine(p1,p2)[0],R1)
    xc = math.sqrt(R1**2 - addb ** 2) + x
    yc = addb + y
    return (xc,yc)

def getDist(p1,p2):
    (x1,y1) = p1
    (x2,y2) = p2
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)
def getLineSector(Opoint,p1,p2,R):
    k1 = getLine(Opoint,p1)[0]
    k2 = getLine(Opoint,p2)[0]
    k = abs(k2 - k1)
    if k == 0 and getLine(p1,p2)[0] == 0:
        return math.pi * R
    elif k == 0:
        return math.pi * R * 0.5
    return R * math.atan(k)

sys.stdin = open("1020.txt","r")
(N,R) = sys.stdin.readline().rstrip().split()
N = int(N)
R = float(R)
coord = []    
for i in xrange(N):
     x,y = sys.stdin.readline().rstrip().split()
     x = float(x)
     y = float(y)
     coord.append((x,y))
sumline = 0
for i in xrange(N):
    j = i + 1
    n = i - 1
    if i + 1 >= N: j = 0
    if i - 1 < 0: n = N - 1
    sumline += getDist(
            getConnect(
                coord[i],
                R,
                coord[j]),
            getConnect(
                coord[j],
                R,
                coord[i]))
#    sumline += 0.5 * getLineSector(
#            coord[i],
#            getConnect(
#                coord[i],
#                R,
#                coord[j]
#                ),
#            getConnect(
#                coord[i],
#                R,
#                coord[n]
#                ),R)
sumline += 2 * math.pi * R
print("%.2f" % sumline)
<file_sep>/solved_2.6/1086.py
#!/usr/bin/python
import sys
import math
def issimple(i):
    for j in xrange(2,math.trunc(math.sqrt(i)) + 1):
        if i % j == 0:
            return False
    return True

countN = int(sys.stdin.readline().rstrip())
N = []
for i in xrange(countN):
    N.append(int(sys.stdin.readline().rstrip()))

simple = [1,2,3]
i = 5
while len(simple) <= 15000:
    if issimple(i):
        simple.append(i)
    i += 2  
for i in N:
    print simple[i]
<file_sep>/unsolved/1195.py
#!/usr/bin/python
import sys

sys.stdin = open("1195.txt")

a = [[[]*3]*3]*3
t = sys.stdin.readlines()
print t
idx = -1
for i in t:
    idx += 1
    (a[idx][0],a[idx][1],a[idx][2] )= i.rstrip()

print a<file_sep>/solved_2.6/1083.py
#!/usr/bin/python

import sys,math

line = sys.stdin.readline().rstrip()
(n,kf) = line.split()
k = len(kf)
n = int(n)
del kf
N = 1
i = 0
for i in xrange(n // k):
    N *= (n - i * k)
if n % k != 0:
    N *= n % k

print N
<file_sep>/unsolved/1302.py
#!/usr/bin/python
import math

def layer(n):
    if int(math.sqrt(n)) ** 2 == n:
        return int(math.sqrt(n))
    else:
        return int(math.sqrt(n)) + 1

def gethorlayer(n):
    return (layer(n) ** 2 - n) // 2 + 1

def moveLeft(i):
    if i != (layer(i) - 1) ** 2 + 1:
        return i - 1
    else:
        return None
def moveRight(i):
    if i != layer(i) ** 2:
        return i + 1
    else:
        return None
def moveUp(i):
    return (layer(i) - 2) ** 2 + i - (layer(i) - 1) ** 2  - 1
def moveDLeft(i):
    if (i - (layer(i) - 1) ** 2) % 2 == 0:
        return moveUp(i)
    else:
        return moveUp(moveLeft(i))
def moveDRight(i):
    if (i - (layer(i) - 1) ** 2) % 2 == 0:
        return moveUp(i)
    else:
        return moveUp(moveRight(i))



a = raw_input().rstrip().split(" ")
for i in xrange(len(a)):
    a[i] = int(a[i])
n = max(a)
m = min(a)
del a
lm = layer(m)
ln = layer(n)
i = n
step = 0


# GET split level of n
##d = []
##for L in xrange(1,ln + 1):
##    l = gethorlayer(n)
##    if l <= L: 
##        d.append(L**2 - 2*(l - 1))
##        if l != L:
##            d.append(L**2 - 2*(l - 1) - 1)
##del d[d.index(n)]
##d.sort()
###print d
##a = [abs(x - m) for x in d]
##step = len(a[a.index(min(a)):]) + min(a)
###print min(a), a[a.index(min(a))]

# ERRO<file_sep>/unsolved/1118.py
#!/usr/bin/python
import math
def getTriv(N):
    ans = []
    for i in xrange(1,N // 2 + 1):
        if N % i == 0:
            ans.append(i)
    return sum(ans) / (0.0 + N)

def getDelit(N):
    ans = [1]
    M = N
    m = int(math.sqrt(N)) + 1
    i = 2
    while 2 <= i <= m:
        while M % i == 0:
            ans.append(i)
            M = M / i
        i += 1
    if M != N:
        ans += [M]
    tans = []
    while tans != ans:
        tans = ans[:]
        ans = expand(ans,N)
    #print "N = ",N," M = ",M," ans = ",ans
    return ans
    
def expand(d,N):
    #d = list(set(d))
    #print d
    l = len(d)
    a = d[:]
    for i in xrange(1,l):
        for j in xrange(i,l):
            if N % (d[i] * d[j]) == 0 and d[i] * d[j] < N:
                a.append(d[i] * d[j])
    return sorted(list(set(a)))
        
(I, J) = raw_input().rstrip().split(" ")
I = int(I)
J = int(J)
minn = None
mint = 10000
i = J
step = -1
while I <= i <= J: 
    #print i
    if I == 1:
        minn = 1
        break
    delit = getDelit(i)
    if len(delit) == 1:
        if (1 / (1.0 + i) <= mint):
            minn = i
            break
    triv = sum(delit) / (0.0 + i)
    #print i, delit,triv
    if triv <= mint:
        mint = triv
        minn = i
    if i % 2 != 0 and step != -2:
        step = -2
    i += -1
print minn
<file_sep>/solved_2.6/1025.py
#!/usr/bin/python
import sys
sys.stdin = open("1025.txt","r")
N = input()
p = [int(x) for x in raw_input().rstrip().split(" ")]

p.sort()
ans = 0
sp = sum(p)
lp = len(p)
t = 0
while t < 0.5 * lp:
    j = p.pop(0)
    ans += j // 2 + 1
    t += 1

print ans
<file_sep>/solved_2.6/1001.py
#!/usr/bin/python
import sys,math,re
sys.stdin = open("1001.txt","r")
a = re.sub("\s+"," ",sys.stdin.read().replace("\n"," ")).split(" ")
while "" in a:
    del a[a.index("")]
for i in xrange(len(a) - 1,-1,-1):
    print "%.4f" % math.sqrt(float(a[i]))
<file_sep>/unsolved/1506.py
#!/usr/bin/python

import sys
#sys.stdin = open("1506.txt")

def tospace(s):
    return " " * (4 - len(s)) + s

(N,K) = sys.stdin.readline().rstrip().split(" ")
N = int(N)
K = int(K)
arr = sys.stdin.readline().rstrip().split(" ")
for i in xrange(len(arr)):
    arr[i] = tospace(arr[i])
#print arr
i = 0
stolb = 1
for i in xrange(1,N):
    if i * K >= N:
        stolb = i
        break
#print stolb
i = 0
if K == 1:
    stolb = N
while i < stolb:
#for i in  xrange(K):
    s = ""
    j = 0
    while i + j * stolb < N:
        # join all arr[i + K * j]
        try:
            s = s + arr[i + j * stolb]
        except:
            pass
        #print i + (N//K) * j, arr[i +  (N // K) * j]
        j += 1   
    print s
    i += 1
    
<file_sep>/unsolved/1642.py
#!/usr/bin/python
import sys

def getDistSimple(path,ppr,ppl):
    global x
    coord = 0
    i = 0
    if path == 1:
        pp = 1
    else:
        pp = -1
    while coord != x:
        if pp == 1:
            bord = ppr
        else:
            bord = ppl
        while coord != bord :
            coord +=  pp
            i += 1
            if coord == x:
                break
        pp *= -1
    return i

#sys.stdin = open("1642.txt","r")
(n,x) = (int(x) for x in sys.stdin.readline().rstrip().split(" "))
p = [int(j) for j in sys.stdin.readline().split()]
ppr = 1000
ppl = -1000
for i in xrange(len(p)):
    if p[i] < ppr and p[i] > 0:
        ppr = p[i]
    if p[i] > ppl and p[i] < 0:
        ppl = p[i]
dist = 0
if x > ppr or x < ppl:
    print  "Impossible"
else:
    print getDistSimple(1,ppr,ppl), getDistSimple(-1,ppr,ppl)
