Number to Word

# Python code for 8315. Number to Word Problem code: NUMWORD

t="teen"
N="nine"
S="seven"
U={0:'zero' ,1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:S,8:'eight',9:N,10:'ten',11:'eleven',12:'twelve',13:'thir'+t,14:'four'+t,15:'fif'+t,16:'six'+t,17:S+t,18:'eigh'+t,19:N+t,20:'twenty',30:'thirty',40:'forty',50:'fifty',60:'sixty',70:S+'ty',80:'eighty',90:N+'ty',100:'hundred',1000:'thousand'}
def f(m):return U.get(m)
n=input()
b=len(str(n))-1
T=10
if b>3:b=3
k=T**b
if b==0:print f(n),
while n:
    m=n/k
    if k==T:
        m=n/T
        s=n%T
        if s:
            x=f(m*T+s)
            if x:print x,
            else:print f(m*T),f(s),
        else:print f(m*T),  
    if k>T:
        x=f(m)
        y=f(k)
        if x:
            if m:print x,y,
        else:
            x=m/T
            z=m%T
            X=f(x*T)
            if z:print X,f(z),y,
            else:print X,y,      
    n%=k
    if n==0:print
    k/=T

Tiling a Grid With Dominoes

# Python code for 2530. Tiling a Grid With Dominoes Problem code: GNY07H

def tiles(n):
    a = [1,1,5,11,36,95,281]
    if n<7:
        return a[n]
    else:
        i=7
        while i!=n+1:
            k=a[i-1]+5*a[i-2]+a[i-3]-a[i-4]
            a.append(k)
            i+=1
    return a[n]           
h=input
for t in range(h()):
    n =h()
    print t+1, tiles(n)

Size Contest

#Python code for 378. Size Contest Problem code: SIZECON
c=0
i=input
exec'b=i();c+=b*(b>0);'*i()
print c

Word To Number

#Python code for  7225. Word To Number Problem code: WORDNUM


import re
c="teen";s="seven";e="eigh";n="nine";f="four";X="six";T="thir";y="ty"
U ={'zero':0,'one':1,'two':2,'three':3,f:4,'five':5,X:6,s:7,e+'t':8,n:9,'ten':10,'eleven':11,'twelve':12,T+c:13,f+c:14,'fif'+c:15,X+c:16,s+c:17,e+c:18,n+c:19,'twen'+y:20,T+y:30,'for'+y:40,'fif'+y:50,X+y:60,s+y:70,e+y:80,n+y:90}
M={'thousand':1000,'hundred':100}
def x(s):
 a=re.split(r"[\s-]+",s)
 n=g=0
 for w in a:
  x=U.get(w)
  if x:
   g+=x
  x=M.get(w)
  if x:n+=g*x;g=0
 print n+g
for t in range(input()):x(raw_input())

Pizza

#Python code for  7169. Pizza Problem code: EGYPIZZA

import math
m=0
n=0
k=0
test=input()
i=0

while i!=test:
    a=raw_input()

    if len(a)!=0:
        if a=="3/4":
            m=m+1
        if a=="1/2":
            n=n+1       
        if a=="1/4":
            k=k+1
        i=i+1           
if m>=k:
    ans=math.ceil(m+n/2.0)

elif m<k:
    k=k-m
    if n%2==0:
        ans = math.ceil(m+n/2.0+k/4.0)
           
    else:
        k=k-2
        ans= math.ceil(m + n/2.0 + k/4.0)

print  int(ans+1)       

GCD (very large numbers)

#Python code to find GCD of two very large numbers

for i in range(input()):
    a,b = [long(i) for i in raw_input().split()]
    while b :
        a,b = b,long(a%b)
    print a

Binary GCD

#Python code to find GCD of two numbers using Binary GCD algorithm

def gcd (a,b):
    if a==0:
        return b
    if b==0:
        return a
   
    shift=0
   
    while (a|b)&1 ==0:
        a>>=1
        b>>=1
        shift+=1
   
    while a&1==0:
        a>>=1
           
    while b:
        while b&1==0:
            b>>=1
        if a>b:
            t=a
            a=b
            b=t
       
        b=b-a
       
    return a<<shift               
   

for i in range(input()):
    a,b=raw_input().split()
    n=int(a)
    m=int(b)
   
    print gcd(n,m)   

Armstrong number

#Python code to print the armstrong numbers in a given range
def armstrong(n):
    m=n
    digits=0
    while m>0:
        digits+=1
        m/=10
    m=n
    N=0
    while m>0:
        N+=pow(m%10,digits)
        m/=10
    if n==N:
        return 1
    else:
        return 0
               
for num in range(1000):
    if armstrong(num+1)==1:
        print num+1                           

Street Parade

#Python code for  95. Street Parade Problem code: STPAR

import re
while 1:
    a=[]
    s=[]
    b=input()
    if b==0:
        break
    else:
        p=1
        for x in re.sub("[^\w]"," ",raw_input()).split():
            a.append(int(x))       
       
        s.append(a[0])
       
        for i in range(1 , b ):
            k=len(s)
            while a[i]>s[k-1] and s[k-1]==p:
                s.pop()
                p+=1
                k=len(s)
                if k==0:
                    break
            s.append(a[i])
       
        k=len(s)   
        while s[k-1]==p:
            s.pop()
            p+=1
            k=len(s)
            if k==0:
                break
   
        if len(s)==0:
            print "yes"
        else:
            print "no"                    

Sieve of Eratosthenes

#Python code to find all primes in given range using Sieve of Eratosthenes algo.

def Sieve_of_Eratosthenes(n):
    composites=[]
    primes=[]
    for a in range(2, n+1):
        if a not in composites:
            primes.append(a)
        for b in range(a*a, n+1,a):
            composites.append(b)
    return primes       
print Sieve_of_Eratosthenes(1000)

28 digits of phi (Golden ratio)

#Python code to computer first 28 digits of golder ration (phi)

from decimal import*
def babylonian(m):
    n=m
    xn=2
    yn=3
    error=Decimal(10**(-323))
    #print error
    while abs(yn-xn)>error:
        xn=Decimal(yn)
        yn=Decimal((xn+n/xn)/2)
    return Decimal(yn)
print (1+babylonian(5))/2       

To read more on Golden ratio......     

27 digits of e (Euler's number)

from decimal import Decimal
def fact(n): 
    if n == 0: 
        return 1 
        else: 
            return n*fact(n-1) 

def euler():
    i=0
    total=0
    n=0
    while i!=170:
        k=fact(n)
        total=Decimal(total+10**100/k)
       
        n+=1
        i=i+1
    return total    /10**100
       
ans=Decimal(euler())
print ans

To read more on Euler's number....

Lucas number

def Lucas(n):
    a=[]
    i=0
    while i!=n+1:
        if i==0:
            a.append(2)
        elif i==1:
            a.append(1)
        else:
            a.append(a[i-1]+a[i-2])
        i+=1   
    return a[n]       

print Lucas(input())


Read more about Lucas Number..           

1 Lac Digits of Pi

def arccot(x, dig):
    powx=total=10**(11+dig)/x
    n=3
    sign=term=-1
    while term:
        powx /= x*x
        term=powx / n
        total+=sign*term
        n+=2
        sign=-sign
    return total/pow(10,10)
   
def pi(dig):
    pi=4 * (4*arccot(5, dig) - arccot(239, dig)) #Machin's Formula
    return pi/10

print pi(100000)       

Cube Root Truncation

291. Cube Root Problem code: CUBERT

def lower_bound(high,low, n):
    while low<=high:
        mid= (low+high)/2
        a= mid*mid*mid
        b=(mid+1)*(mid+1)*(mid+1)
   
        if a==n or (a<n and b>n):
            return mid
        elif a<n:
            low=mid+1
        else:
            high=mid-1
    return mid
i=0
t=input()
while i<t:
     s1=raw_input()
     if(len(s1)>0):
           i+=1  
           n=long(s1)
           ans1=long(pow(n,1/3.0))
          
           k=long(pow(n,1/2.0)*pow(10,10))
           n*=pow(10,30)
        
           ans=lower_bound(k,long(ans1 *pow(10,10)),n)
           ans=str(ans)
           root=ans[:-10]+"."+ans[-10:]
           count=0
           for c in root:
                  if(c>='0' and c<='9'):
                        count=(count%10+int(c))%10
           final=str(count)+" "+root
           print(final)

Heptadecimal Numbers

7108. Heptadecimal Numbers Problem code: HEPNUM
while 1:
    a,b=raw_input().split()
    if a=='*' and b=='*':break
    m=len(a)
    n=len(b)
    if m<n:a=(n-m)* '0'+a
    elif n<m:b= (m-n)*'0'+b           
    if a>b:print ">"
    elif a==b:print "="
    else:print "<"            

Last Non-Zero Digit of Factorials

2124. Last Non-Zero Digit of Factorials Problem code: FCTRL4

def P(k):
    A=[6,2,4,8]
    if k<1:
        return 1
    else:
        return A[k%4]

def L(N):
    A=[1,1,2,6,4]
    if N<5:
        return A[N]
    else:
        return (P(N/5)*L(N/5)*L(N%5))%10

while True:
    try:
        a= raw_input()
        print L(int(a))       
    except EOFError:
        break

8057. Square Free Factorization Problem code: AMR10C

# Square-Free Factorization

prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 ,1009 ,1013]
def free_square_factors(n):
    root = pow(n,0.5)
    ret=0
    i=0
    while prime[i]<=root:
        if n%prime[i]==0:
            count=0
            while n%prime[i]==0:
                count +=1
                n/=prime[i]
            root=pow(n,0.5)
            if count>ret:   
                ret= count
        i+=1
    if n>1 and ret<1:
        ret = 1
    return ret
for t in range(input()):
    n=input()
    print free_square_factors(n)

10373. Help Balaji! Problem code: ABA12A

for j in range(input()):
    a,c=raw_input().split()
    print c

42. Adding Reversed Numbers Problem code: ADDREV

def r(n):
    s=0
    while n>=1:
        a=n%10
        s=s*10+a
        n/=10
    return s

for i in range(input()):
    x,y=raw_input().split()
    print r(r(int(x))+r(int(y)))