How to implement Short Quines in C?

1) Quine Using Macros :

#define Z(x)t=#x;x

Z(main(){printf("#define Z(x)t=#x;x\nZ(%s)",t);})

2) Use a variable without declaring

b;main(a,s){printf(s="b;main(a,s){printf(s=%c%s%c,34,s,34,a,b);}",34,s,34,a,b);}

In the above quine, there is no need to declare s char *s

3) Initialize variables without assigning values explicitly

b;main(a,s){printf(s="b;main(a,s){printf(s=%c%s%c,34,s,34,a,b);}",34,s,34,a,b);}

In the above quine, a and b are integer variables initialized to 1 and 0 respectively.

4) Use ternary operators if possible

#define Z(x)t=#x;x

Z(main(i){for(;12%++i;);printf(i-12?"#define Z(x)t=#x;x\nZ(%s)":"YES",t);})

The above program acts as a quine if a number is composite else prints “Yes”.

Replace 12 by other numbers to check.

5) Use logical operators:

Example :

The code :

if(n%2==0)

n=n/2;

else

n=n*2;

printf(“%d\n”, n);

can be rewritten as :

printf("%d\n", n%2?n*2:n/2);

Shortest Quine Ever in Python

(Hint: empty source file)

Sorted subsequence of size 3 in O(n) time and O(n) extra space

#include<stdio.h>
#include<stdlib.h>
void size3Subsequence(int arr[], int n)
{
    int max = n-1, min=0, i;
     int *smaller = (int*)malloc(sizeof(int)*n);
     smaller[0] = -1;
     for (i = 1; i < n; i++)
    {
        if (arr[i] <= arr[min])
        {
            min = i;
            smaller[i] = -1;
        }
       
        else
            smaller[i] = min;
   }

    for (i = n-2; i >= 0; i--)
    {
        if (arr[i] >= arr[max])
            max = i;

        else if(smaller[i]!=-1)
        {
            printf("%d %d %d\n", arr[smaller[i]], arr[i], arr[max]);
                free(smaller);
            return;
        }  
    }

    printf("No such triplet found\n");
    free(smaller);
    return;
}

int main()
{
    int arr[] = {1,3,0, 2, 5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    size3Subsequence(arr, n);
    return 0;
}

Maximum of all subarrays of size k in O(n) time and O(1) extra space !!

#include<stdio.h>
#include<limits.h>

void printKMax(int *arr, int n , int k)
{
    int max=INT_MIN, sec_max=INT_MIN, tag=0,cnt=0;
    int i, max_i, sec_max_i;
   
    for(i=0;i<n;i++)
    {
        if(arr[i]>=max)
        {
            max = arr[i];
            max_i=i-cnt;
        }
       
        else if(arr[i]>=sec_max)
        {
            sec_max = arr[i];
            sec_max_i=i-cnt;
        }
       
        if(i==k-1)
            tag=1;
       
        if(tag)
        {
            cnt++;
            printf("%d ", max);
                   
            max_i--;
            sec_max_i--;
           
            if(max_i==-1)
            {
                max_i = sec_max_i;
                max=sec_max;
                sec_max = INT_MIN;
            }
        }
    }
        printf("\n");
}

int main()
{
    int arr[] ={3,7,1,213, 12, 312};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    printKMax(arr, n, k);
    return 0;
}

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)

Househoder Method and Jacobi Rotaion

/* C code to tridiagonalize a Matrix using Householder's Method and then finding the eigen values using Jacobi Rotation Method*/

#include<stdio.h>
#include<math.h>
#define ERROR 0.0000001
//Function to read input matrix
void read_matrix(int order ,float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
        for (j=0;j<order;j++)
            scanf("%f",&matrix[i][j]);
}

//Function to print the matrix
void print_matrix(int order , float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
    {
        for (j=0;j<order;j++)
            printf("%.4f\t",matrix[i][j]);
        printf("\n");
    }
}

int check_symmetric(int n , float a[][n])
{
    int i, j, tag=1;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if (a[i][j]!=a[j][i])
            {
                tag=0;
                break;
            }   
        }
       
        if (tag==0)
            break;
    }

    return tag;
}

//Function to multiply two matrices "a" and "b" and put the result in matrix "c"
float multiply(int n , float a[][n], float b[][n] , float c[][n] )
{
    int i,j,k ;
    float sum;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            sum=0;
            for(k=0;k<n;k++)
                sum=sum+(a[i][k])*(b[k][j]);
            c[i][j]=sum;
        }
}   

/*Function to get an identity matrix*/
void identity(int n , float S[][n])
{
    int i , j;
    for (i=0; i<n;i++)
        for (j=0;j<n;j++)
        {
            if (i==j)
                S[i][i]=1;
            else
                S[i][j]=0;   
        }
}

/*Function to copy one matrix into another matrix*/
void copy(int n, float a[][n] , float b[][n])
{
    int i , j;
    for (i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[i][j]=b[i][j];
}

void transpose_vector(int n, float vector[] , float matrix[][n])
{
    int i,j;
    float sum=0;
   
    for(i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            matrix[i][j] = vector[i]*vector[j];
        }
    }
}

void print_vector(int n, float a[])
{
    int i;
    for (i=0;i<n;i++)
    {
        printf("%12.4f  ",a[i]);
    }
    printf("\n");   
}

void swap(float a[], int i, int j)
{
    float temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

void bubblesort( int n, float a[])
{
    int i , j;
     for(j=n-2;j>=1;j--)
         for(i=0;i<=j;i++)
             if(a[i]>a[i+1])
                 swap(a,i,i+1);        
}

void jacobi_rotation(int n , float a[][n])
{
    int i,j;
    float pi = 3.1415926;
    float S[n][n] , invS[n][n] ,temp1[n][n] ,temp2[n][n], theta;   

    identity(n,S);
    identity(n,invS);

    int u,v,tag=1;
    while(1)
    {
        tag=1;
        for (i=0;i<n;i++)
        {
           
            for (j=i+1 ; j <n;j++)
            {
                if ((a[i][j])!=0)
                {
                    if (a[i][i]!=a[j][j])
                        theta = (atan(2*a[i][j]/(a[i][i]-a[j][j])))/2;

                    else
                    {
                        if (a[i][j]>0)
                            theta = pi/4;
                       
                        else if (a[i][j]<0)
                            theta = -pi/4;
                    }
                                           
                   
                    identity(n,S);
                    identity(n,invS);

                    S[i][i]= invS[i][i]= invS[j][j]=S[j][j]=cos(theta);
                    S[i][j]= invS[j][i]= -sin(theta);
                    S[j][i]= invS[i][j]=  sin(theta);

                    multiply(n,invS,a,temp1);
                    multiply(n,temp1,S,temp2);
   
                    copy(n,a,temp2);
                   
                }
                else continue;
            }   
        }   
   
        for (u=0;u<n;u++)
        {
            for (v=u+1;v<n;v++)
            {
                if (abs(a[u][v]) > ERROR)
                {
                    tag=0;
                    break;
                }   
            }
            if (tag==0)
                break;
        }
   
        if (tag==1)
            break;
   
    }   
}


/*main function*/
int main()
{
    int n,i,j,sign,k;
    scanf("%d",&n);

    float a[n][n] , P[n][n] ,temp1[n][n] ,temp2[n][n] , I[n][n] , w[n], transpose[n][n], x , sum,s,temp;
    read_matrix(n,a);

    int check;
    check = check_symmetric(n,a);
    if (check==0)
    {
        printf("Given matrix is not symmetric\n");
        return 0;
    }
   
    for(i=0;i<n-2;i++)
    {
        j=0;
        sum=0;
        while(j<=i)
        {
            w[j++]=0;
        }
       
        for(k=i+1;k<n;k++)
            sum=sum+a[i][k]*a[i][k];   
       
        s= sqrt(sum);
        if (s==0)
            continue;
        //printf("s : %f\n",s);
        if (j==i+1)
        {
            if (a[i][j]<0)
                sign=-1;
            else
                sign=1;
               
            temp = (1+a[i][j]*sign/s)/2;
            x=sqrt(temp);
            w[j]=x;
            j++;
        }
       
        for (j=i+2;j<n;j++)
        {
            w[j]=(a[i][j]*sign)/(2*s*x);
        }
       
        identity(n, I);
        transpose_vector(n,w,transpose);
       
        for(k=0;k<n;k++)
        {
            for(j=0;j<n;j++)
            {
                P[k][j]=I[k][j]-2*transpose[k][j];
            }
        }

        //print_matrix(n, P);

        multiply(n,a,P,temp1);
       
        multiply(n,P,temp1,temp2);       
        copy(n,a,temp2);
       
        //print_matrix(n, a);
    }
   
    //printf("\nTridiagonal matrix using Householder Method is : \n\n");
    //printf("\n");
    print_matrix(n,a);
   
    //printf("\nEigne values of Tridiagonal  : \n\n");
    jacobi_rotation(n, a);

    float eigen[n];
    for (i=0;i<n;i++)
        eigen[i]=a[i][i];
       
    bubblesort(n,eigen);   
    //printf("\n");
    for (i=n-1;i>=0;i--)
        printf("%.4f\n",eigen[i]);
   
    return 0;   
}

Circular Track

// C code for 9199. Circular Track Problem code: SPEED

#include<stdio.h>
int gcd(int a, int b)
{
    int r ;
        while (b!=0)
        {
            r=a%b;
            a=b;
            b=r;
        }
        return a;
}

int main()
{
    int t,m,n,ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        ans=m>n?m-n:n-m;
        m*=(m<0?-1:1);
        n*=(n<0?-1:1);
        printf("%d\n",ans/(gcd(m,n)));
    }
    return 0;
}

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

Tanks

// C code for  13675. Tanks Problem code: NEWTANK

#include<stdio.h>
int main()
{
    int test,v,t,i;
    scanf("%d",&test);
    for(i=1;i<=test;i++)
    {
        scanf("%d%d",&v,    &t);
        printf("Case #%d: %d\n",i,v*t);
    }
    return 0;
}

H Number

// C code for 13662. H Number Problem code: HNUM

#include<stdio.h>
int main()
{
    int test, n,i;
    scanf("%d",&test);
   
    for(i=1;i<=test;i++)
    {
        scanf("%d",&n);
        if (n%30==0)
            printf("Case #%d: H-Number\n",i);
        else
            printf("Case #%d: Not H-Number\n",i);   
    }
    return 0;
}

Azooz

// C code for 13677. Azooz Problem code: AZOOZ

#include<stdio.h>
int main()
{
    int t,n,i,j,k;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        k=1;
        scanf("%d",&n);
        k=3*(n*(n+1)/2);
       
        printf("Case #%d: %d\n",i,k);   
    }
    return 0;
}

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

Egypt

// C code for 9754. Egypt Problem code: SCPC11D

#include<stdio.h>
int main()
{
    int a,b,c;
   
    scanf("%d%d%d",&a,&b,&c);
    while(a&&b&&c)
    {
        if (a>b&&a>c&&b*b+c*c==a*a)
            printf("right\n");
       
        else if (b>c && b>a && c*c+a*a==b*b)   
            printf("right\n");
       
        else if (a*a+b*b==c*c)
            printf("right\n");
        else
            printf("wrong\n");       
   
        scanf("%d%d%d",&a,&b,&c);       
    }
    return 0;
}

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)   

GCD2

// C code for  2906. GCD2 Problem code: GCD2

#include <stdio.h>

 int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

int mod(char s[],int d)
{
    int r = 0,i;

    for(i=0;s[i];i++)
    {
        r=10*r +(s[i] - 48);
        r %= d;
    }
    return r;
}

int main()
{
    int test , a;
    char b[254];

    scanf("%d",&test);

    while(test--)
    {
        scanf("%d%s",&a,b);
   
        if(!a)
            printf("%s\n",b);
       
        else
            printf("%d\n",gcd(a,mod(b,a)));
    }
    return 0;
}

Euler Totient Function

//C code for 4141. Euler Totient Function Problem code: ETF

#include<stdio.h>
int totient(int n)
{
    int i, ans = n;
   
    for (i=2;i*i<=n;i++)
    {
        if (n%i==0)
            ans-=ans/i;
           
        while(n%i==0)
            n/=i;
    }   
   
    if (n!=1)
        ans-=ans/n;
    return ans;   
}       
   
int main()
{
    int test ,n;
   
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&n);
        printf("%d\n",totient(n));
   
    }
    return 0;
}

Cards

// C code for  10509. Cards Problem code: CRDS

#include<stdio.h>
int main()
{
    int t;
    long long n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lld",&n);
        printf("%lld\n",(n*(3*n+1)/2)%1000007);   
    }
    return 0;
}

Recaman’s Sequence

// C code for 3934. Recaman’s Sequence Problem code: MRECAMAN

#include <stdio.h>
#define max 500000

int tag[10*max+1] ,a[2*max+1];
int main()
{
    int i, n, m;
    for(i=1; i<=max; i++)
    {
        m = a[i-1];
        a[i]= m > i && !tag[m-i]?m - i:m + i;
        tag[a[i]] = 1;
    }
    while(scanf("%d", &n)==1 && n!=-1)
        printf("%d\n", a[n]);
           
        return 0;
}

A Game with Numbers

// C code for 1419. A Game with Numbers Problem code: NGM

#include<stdio.h>
int main()
{
    int n;
    while (scanf("%d",&n)==1)
        (n%10)?(printf("1\n%d\n",n%10)):(printf("2\n"));
    return 0;
}

Binary Stirling Numbers

//C code for 106. Binary Stirling Numbers Problem code: BINSTIRL

#include <stdio.h>
int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", !((n-m)&((m-1)/2)));
    }
    return 0;
}

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                           

Ambiguous Permutations

 //C code for 379. Ambiguous Permutations Problem code: PERMUT2

#include<stdio.h>
int main()
{
    int a[100002],b[100002],n,tag,i,x;
    while(1)
    {
        tag=1;
        scanf("%d",&n);
   
        if (n==0)
            break;
   
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[i]=x;
            b[a[i]]=i;
        }   

        for (i=1;i<=n;i++)
            if (a[i]!=b[i])
            {
                tag=0;
                break;
            }
        if (tag==0)
            printf("not ambiguous\n");
        else   
            printf("ambiguous\n");
    }   
    return 0;
}

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

Tridiagonalization using Given's Method

#include<stdio.h>
#define max 1000
#include<math.h>

//Function to read input matrix
void read_matrix(int order ,float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
        for (j=0;j<order;j++)
            scanf("%f",&matrix[i][j]);
}

//Function to print the matrix
void print_matrix(int order , float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
    {
        for (j=0;j<order;j++)
            printf("%f\t",matrix[i][j]);
        printf("\n");
    }
}

//Function to multiply two matrices "a" and "b" and put the result in matrix "c"
float multiply(int n , float a[][n], float b[][n] , float c[][n] )
{
    int i,j,k ;
    float sum;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            sum=0;
            for(k=0;k<n;k++)
                sum=sum+(a[i][k])*(b[k][j]);
            c[i][j]=sum;
        }
}   

/*Function to get an identity matrix*/
void identity(int n , float S[][n])
{
    int i , j;
    for (i=0; i<n;i++)
        for (j=0;j<n;j++)
        {
            if (i==j)
                S[i][i]=1;
            else
                S[i][j]=0;   
        }
}

/*Function to copy one matrix into another matrix*/
void copy(int n, float a[][n] , float b[][n])
{
    int i , j;
    for (i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[i][j]=b[i][j];
}

/*main function*/
int main()
{
    int n,i,j;

    printf("Enter the order of matrix : ");
    scanf("%d",&n);
    float a[n][n] , S[n][n] , invS[n][n] ,temp1[n][n] ,temp2[n][n];   
    read_matrix(n,a);

    identity(n,S);
    identity(n,invS);

    for (i=0;i<=n-3;i++)
    {
        for (j=i+2 ; j <= n-1;j++)
        {
            if ((a[i][j])!=0)
            {
                float theta = atan(a[i][j]/a[i][i+1]);

                identity(n,S);
                identity(n,invS);

                S[i+1][i+1]= invS[i+1][i+1]= invS[j][j]=S[j][j]=cos(theta);
                S[i+1][j]= invS[j][i+1]= -sin(theta);
                S[j][i+1]= invS[i+1][j]=  sin(theta);

                multiply(n,invS,a,temp1);
                multiply(n,temp1,S,temp2);
   
                copy(n,a,temp2);
            }
            else continue;
        }   
    }   
    print_matrix(n,a);
    return 0;   
}

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

9722. Insertion Sort Problem code: CODESPTB

#include<stdio.h>
int ans;
void merge(int a[] , int left , int mid , int right)
{
    int temp[200000];
    int i=left, j=mid+1 , k=0;
   
    while((i<=mid)&&(j<=right))
    {
        if(a[i]<=a[j])
            temp[k++]=a[i++];
   
        else
        {
            ans=ans+mid-i+1;
            temp[k++]=a[j++];
       }
    }
   
    while(i<=mid)
        temp[k++]=a[i++];
  
    while(j<=right)
        temp[k++]=a[j++];
  
    for(i=0;i<k;i++)
        a[left+i]=temp[i];
}

void merge_sort(int a[],int left,int right)
{
    int mid;
   
    if(left>=right)
        return;
   
    else
    {
        mid=(left+right)/2;
        merge_sort(a,left,mid);
        merge_sort(a,mid+1,right);
        merge(a,left,mid,right);
    }
}


int main()
{
    int a[200000];
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
       
        merge_sort(a,0,n-1);
        printf("%d\n",ans);
    }
    return 0;
}

11. Factorial Problem code: FCTRL

#include <stdio.h>
int main()
{
    long long int ans,num,test;
    scanf("%d",&test);

    while(test--)
    {
        scanf("%lld",&num);
        ans=0;
        while(num)
        {
            num/=5;
            ans += num;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

11932. Amz Rock Problem code: AMZRCK

p=5**.5;f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
i=input
for j in range(i()):
 print int(f(i()+2))

5917. Factorial length Problem code: LENGFACT

#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
    double num, length, pi = acos(-1.0);
    int t;
    scanf("%d", &t);
    while(t--)
        scanf("%lf", &num),printf("%.0lf\n", num<3.0? 1.0 : floor((num*log(num)-num+(log(2.0*pi*num))/2.0)/log(10.0))+1.0 );
    return 0;
}

2148. Candy III Problem code: CANDY3

#include<stdio.h>
int main()
{
    long long int t , n , i ,sum ;
    scanf("%lld", &t);
    while(t--)
    {
        sum=0;
        printf("\n");
        scanf("%lld",&n);
        long long int a[n];
        for (i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            sum =sum+a[i];
            sum=sum%n;
        }

            if(sum==0)
                printf("YES\n");
           
            else
                printf("NO\n");   
    }
    return 0;
}

23. Pyramids Problem code: PIR

#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    double  a,b,c,d,e,f,A,B,C,D,E,F;
    double vol;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf",&a,&c,&e,&b,&d,&f);
        A=a*a;
        B=b*b;
        C=c*c;
        D=d*d;
        E=e*e;
        F=f*f;
        vol = sqrt((-A*B*C - A*D*E - B*D*F - C*E*F + A*C*D + B*C*D + A*B*E + B*C*E + B*D*E +C*D*E + A*B*F + A*C*F +A*D*F + C*D*F + A*E*F + B*E*F - C*C*D - C*D*D - B*B*E - B*E*E- A*A*F - A*F*F)/144.0);
        printf("%.4lf\n",vol);   
    }
    return 0;
}

2523. Mispelling Problem code: GNY07A

#include<stdio.h>
#include<math.h>
int main()
{
    char c;
    int d,i,j,ct,n;
    scanf("%d",&n);
    ct =1;
    for(j=1;j<=ceil(2*n);j++)
    {
        scanf("%d",&d);
        i=1;
        while((c=getchar())!='\n'&& c!=' ' )
        {
            if (i==1)
                printf("%d ",j/2);
             if (c!=' ' && i!=d)
                printf("%c",c);           
            i++;
        }
            printf("\n");
    }
    return 0;
}

7406. Beehive Numbers Problem code: BEENUMS

while 1:
    n=input()
    if n==-1:
        break
    k=float((-3+pow(-3+12*n,1.0/2))/6)
    d=int(k)
    if d-k==0:
        print "Y"
    else:
        print "N"   

7733. Happy Numbers I Problem code: HPYNOS

Squares = dict([(m, int(m)**2) for m in "0123456789"])
def is_happy(n):
  s = []
  count=0
  while n not in s:
      if n==1:
          return count
        s.append(n)
        n = sum(Squares[digits] for digits in str(n))
        count +=1
  return -1
print is_happy(input())

450. Enormous Input Test Problem code: INTEST

#include<stdio.h>
int main()
{
    long long int n,k,x,c=0;
    scanf("%lld%lld",&n,&k);
   
    while(n--)
    {
        scanf("%lld",&x);
        if(x%k==0)
            c++;
    }
    printf("%lld\n",c);
    return 0;
}

1030. Triple Fat Ladies Problem code: EIGHTS

 #include<stdio.h>
int main()
{
    int test;
      long long int k,temp;
      scanf("%d",&test);
   
      while(test--)
      {
          scanf("%lld",&k);
          temp=(k-1)*250+192;
          printf("%lld\n",temp);
      }
      return 0;
}

Bell Number

#To find the nth bell number
a=[]
n=input()
if n==0:
    a.append(1)
else:
    for i in range(1,n+1):
        if len(a)==0:
            a.append(1)
            leng = 1
            start = 0
        else:
            last=a[len(a)-1]
            j=0
            index = start
            while j!=leng:
                element = last+a[index]
                a.append(element)
                index+=1
                j+=1
                last= a[len(a)-1]
            start = len(a) - leng -1   
            leng +=1
print a[len(a)-1]   

10657. LOGIC Problem code: LGIC

import math;a=input();print math.factorial(a)+2**a-a

Perfect Number

////Program to check if a given no. is perfect no.  or not

#include <stdio.h>

/*Function to find the sum of divisors of the number n*/
int sum_of_divisors(n)
{
    int i , sum = 0 ;
   
    for (i=1;i<=n-1;i++)
           if (( n%i )==0)
        sum=sum+i;
    return sum;
}

/*Function to check if the given number is perfect or not by checking the sum of divisors*/
int check_perfect(n)
{
    int sum ;
   
    sum = sum_of_divisors(n);
   
    if (sum==n)
        return 1;
   
    else
        return 0;
}

/*main function*/
int main()
{
    int i , n , check;
   
    printf("enter the no.");
    scanf("%d",&n);

    check = check_perfect(n);
    if (check == 1)
        printf("given no. is perfect no.\n");

    else
        printf ("given no. is not a perfect \n");
}

2523. Mispelling Problem code: GNY07A

#include<stdio.h>
#include<math.h>
int main()
{
    char c;
    int d,i,j,ct,n;
    scanf("%d",&n);
    ct =1;
    for(j=1;j<=ceil(2*n);j++)
    {
        scanf("%d",&d);
        i=1;
        while((c=getchar())!='\n'&& c!=' ' )
        {
            if (i==1)
                printf("%d ",j/2);
             if (c!=' ' && i!=d)
                printf("%c",c);           
            i++;
        }
            printf("\n");
    }
    return 0;
}

8371. TRIANGULAR PRISM Problem code: PRISMSA

i=input
p=pow
for t in range(i()):
    v=i()
    a=p(4*v,1.0/3)
    print 3*a*a*p(3,1/2.0)/2

10676. 0110SS Problem code: IWGBS

N=input()
A=[0,1]
B = [0,1]
i = 2
while i<=N:
    A.append(A[i-1]+B[i-1])
    B.append(A[i-1])
    i +=1
print A[N]+B[N]

10657. LOGIC Problem code: LGIC

import math;a=input();print math.factorial(a)+2**a-a

1025. Fashion Shows Problem code: FASHION

#include<cstdio>
#include<iostream>
#include<algorithm>
#define FOR(i,n) for(i=0;i<n;i++)
#define S(N) scanf("%d", &N)
#define ST(a,N) sort(a, a+ N)
using namespace std;
int main()
{
    int test, N, M, ans, i ,men[1001], women[1001];
    S(test);
    while (test--)
    {
         ans = 0;
         S(N);

         FOR(i,N)
                 S(men[i]);

         FOR(i,N)
                 S(women[i]);

         ST(men,N);
         ST(women,N);

         FOR(i,N)
                 ans += men[i] * women[i];
         printf("%d\n", ans);
    }
        return 0;
}

Kamil

#Python code for  53. Kamil Problem code: KAMIL

for i in 10*[0]:s=raw_input();print 2**sum(s.count(i)for i in'DFLT')

Reversed Number

//  C code to reverse the digits of a user entered number
#include<stdio.h>

/*Function to reverse the digits of a number*/
void reverse_digits(n)
{
    while(n!=0)  
    {
        printf("%d",n%10);
        n=n/10;
    }
}
int main()
{
    int n;
    printf("Enter a no.\n");
    scanf("%d",&n);

    printf("The reverse no.is\n");
    reverse_digits(n);
    printf("\n");
}

Perfect Number

////Program to check if a given no. is perfect no.  or not

#include <stdio.h>

/*Function to find the sum of divisors of the number n*/
int sum_of_divisors(n)
{
    int i , sum = 0 ;
   
    for (i=1;i<=n-1;i++)
           if (( n%i )==0)
        sum=sum+i;
    return sum;
}

/*Function to check if the given number is perfect or not by checking the sum of divisors*/
int check_perfect(n)
{
    int sum ;
   
    sum = sum_of_divisors(n);
   
    if (sum==n)
        return 1;
   
    else
        return 0;
}

/*main function*/
int main()
{
    int i , n , check;
   
    printf("enter the no.");
    scanf("%d",&n);

    check = check_perfect(n);
    if (check == 1)
        printf("given no. is perfect no.\n");

    else
        printf ("given no. is not a perfect \n");
}

Centigrate to Fahrenheit

//Program to convert temperature from degree centigrade to Fahrenheit:
// (f-32)/180 = c/100

#include<stdio.h>

int main()
{
    float c,f;

    printf("enter temp in centigrade:\n ");
    scanf("%f",&c);
   
    f=(1.8*c)+32;
    printf("temp in Fahrenheit=\n%f",f);
    return 0;
}

Diamond Shape

/*C code to print a diamond shape when an odd number is entered*/

#include <stdio.h>

/*Function to check whether the number entered is valid or not*/
int check_validity(n)
{
    if (n%2 ==0 || n<=0)
        return 0;
       
    else
        return 1;
}

/*Function to print upper part of the diamond shape for an odd entered number*/
void diamond_upper_shape(n)
{
    int  i , j ,  m ;

    for (i=1 ; i<=n ; i=i+2)
    {       
        for (m=1 ; m<=(n-i)/2 ; m++)
            printf ("  ");
               
        for (j=1;j<=i;j=j+1)           
            printf (" *");                                           

        printf ("\n");
    }       
}

/*Function to print the lower part of the diamond shape for an odd entered number*/
void diamond_lower_shape(n)
{
    int  i , j ,  m ;
   
    for (i=n-2 ; i>=1 ; i=i-2 )
    {   
        for (m=1 ; m<=(n-i)/2  ; m++)
            printf ("  ");
                                       
        for (j=1 ; j<=i ; j=j+1)
            printf (" *");                                           
                                       
        printf ("\n");   
    }

}
/*main function*/
int main()
{
    int  i , j ,  n  , m ;
   
    printf ("enter an odd no.");
    scanf ("%d",&n);
   
    if (check_validity(n)!=0)
    {
        diamond_upper_shape(n);   
        diamond_lower_shape(n);
    }
   
    else
        printf("Enter an odd number\n");
}

Pascal Triangle

/*Program to print the element of pascal-triangle when the row and column numbers are given.\

pascal triangle:


                1
             1    1
          1    2    1
       1    3    3    1   
    1    4     6    4    1
  ................................
......................................

*/
#include<stdio.h>

int pascal(int a,int b)
{
    if (a==b)
        return 1;

    else if (b==1)
        return 1;
       
    else 
        return pascal(a-1,b-1)+pascal(a-1,b);
}

int main()
{
    int a,b;
   
    printf("Enter row number : ");
    scanf("%d",&a);
   
    printf("Enter column\n number : ");
    scanf("%d",&b);
   
    if ( (b>a)  ||  (b<=0)  ||  (a<=0)  )
        printf("Invalid Entry\n");
   
    else 
        printf("The (%d,%d)th element of pascal triangle is : %d\n",b,a,pascal(a,b));

   return 0;
}

Fibonacci Levels

#include<stdio.h>

/*Print the levels of fibonacci recursion and also returns the fibonacci value*/
int fib(int n,int level)
{
    int i;

    for(i=0;i<4*level;i++)  //a*level adjusts the horizontal space between two levels
        printf(" ");

    printf("fib(%d)\n",n);

    if(n==0)
        return 0;

    else if(n==1)
        return 1;

    else 
        return (fib(n-1,++level))+(fib(n-2,level));    //fib(n) = fib(n-1)+fib(n-2) ; n>=2
}

//main function
int main()
{
    int n , f;
   
    printf ("Enter the no. whose fibonacci no. is to be found;  ");
    scanf("%d",&n);
    
    printf("fib(%d)=%d\n", n , fib(n , 0) );
 
   return 0;
}

Matrix Rotation

// Program to rotate the nxn matrix to the right by 90 degree..
#include<stdio.h>
#define max 100

/*Function to store  the matrix*/
void read_matrix(int a[][max] , int order)
{
    int i , j , n = order-1;
    for (i=0;i<=n;i++)
        for (j=0;j<=n;j++)
           scanf("%d",&a[i][j]);
}


/*Function to rotate a matrix to the right by 90 degress*/
void rotate_right( int a[][max] , int b[][max] , int order)
{
    int i , j , n = order -1;
    for (i=0;i<=n;i++)
        for (j=0;j<=n;j++)   
             b[j][n-i]=a[i][j];
}

/*Function to print the matrix*/
void print_matrix(int a[][max] , int order)
{
    int i  , j , n =  order-1;
    for (i=0;i<=n;i++)
    {
        for (j=0;j<=n;j++)
          printf("%d\t",a[i][j]);
       
        printf("\n");
    }   
}

/*main function*/
int main()
{
    int  i , j , n ;
    int a[max][max];
    int b[max][max];
   
    printf("enter the order of matrix\n");
    scanf ("%d",&n);

    printf ("enter the nxn matrix\n");
    read_matrix (a , n);
    rotate_right( a , b , n);

    printf ("before rotation: \n");
    print_matrix( a , n);
    printf ("\n");

    printf ("after rotation: \n");
    print_matrix(b , n);
    printf("\n");
   
    return 0;
}

Circular Prime

 /* C code to check whether a number obtained by circularly shifting its digits is prime or not*/
#include <stdio.h>
//function for finding the number of digits in a given number
int get_num_digits(n)
{
    int k = 0;
    while (n!=0)
    {
        n = n/10;
        k++;
    }
    return k;
}

//function for finding a circular number
int get_shifted_num(n)
{

    int i , d, k = 1 , last_digit , new_num;

    d= get_num_digits(n);

    for (i=1 ; i<=(d-1); i++)
        k = k*10;

    last_digit = n/k;

    new_num = (n - last_digit*k)*10 + last_digit;
    return new_num;
}

//function to check whether a number is prime or not
 is_prime(n)
{
    int  i , circular_num =n;   
    for (i=1; i<=circular_num/2 ; i++)
        if (circular_num%(i+1) == 0)
                return  0 ;
    return 1;           
}

int main ()
{
    int i , n , d ,  circular_num , z;

    printf("enter a number : ");
    scanf("%d", &n);

    d = get_num_digits(n);
   
    circular_num =n;

    for (i = 1; i<=d ; i++)
    {
        printf ("shifted no. is  : %d\n", circular_num);
        z = is_prime(circular_num);

        if (z==1)
            printf ("%d is prime\n\n", circular_num);
        else
            printf ("%d is not prime: \n\n" , circular_num);

        circular_num = get_shifted_num(circular_num);
    }
    return 0;
}

To and Fro

400. To and Fro Problem code: TOANDFRO

 #include<iostream>
 using namespace std;
 int main()
 {
     int columns,n,m;
     while (1)
     {
            cin>>columns;
            if (columns==0)
                break;
         string s;
         cin >> s;
         string r(s);

         int rows = s.size() / columns;
         for (int i=0; i<s.size(); i++)
         {
            m = i/columns;
            m%2==0?n=i%columns:n = columns-1-i%columns;   
            r[n*rows+m] = s[i];
         }
         cout << r << endl;
     }
     return 0;
 }

1724. Counting Triangles Problem code: TRICOUNT

#include<stdio.h>
int main()
{
        long long int test,n;
        scanf("%lld",&test);
        while(test--)
            scanf("%lld",&n)&&printf("%lld\n",n*(n+2)*(2*n+1)/8);
        return 0;
}

9948. Will it ever stop Problem code: WILLITST

#include<stdio.h>
int main()
{
    long long int  n;
    while(scanf("%lld",&n)!=EOF)
    {
        if((n&(n-1))==0)
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}

2716. Maximal Quadrilateral Area Problem code: QUADAREA

#include<cstdio>
#include<iostream>
#include<math.h>
int main()
{
    int test;
    double a,b,c,d,s,max_area;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
        s=(a+b+c+d)/2;
        max_area=sqrt(((s-a)*(s-b)*(s-c)*(s-d)));
        printf("%0.2lf\n",max_area);
    }
    return 0;
}

Sum the Series

11746. Sum the Series Problem code: SUMUP

for j in[1]*input():
    s,a,b=0,1,3
    for i in range(input()):s+=(b-a)/(b*a*2.0);a=b;b+=2*i+4
    print"{0:.5f}".format(s)

3442. The last digit Problem code: LASTDIG

#include<cmath>
#include<cstdio>
int main()
{
    long long int a , b , n, i , k;
    scanf("%lld", &n);
    for (i=0;i<n;i++)
    {
        scanf("%lld %lld", &a , &b);
               
        if(b==0&&a==0)
            k=1;
        else if (b==0 )
            k=1;
        else if (a==0)
            k=0;
        else
        {                   
            if (b%4==0)
                b = 4;
            else
                b=b%4;
            k = pow(a, b);
        }   
            k = k%10;   
            printf("%lld\n", k);       
    }
    return 0;
}