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;
}

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;
}

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;
}

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;
}

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;
}

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;   
}

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;
}

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;
}

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;
}