MAXLN

MAXLN


#include<iostream>
using namespace std;

int main(){
    int T,r;
    long long s;
   
    scanf("%d",&T);
   
    for(int tc = 1;tc <= T;++tc){
        scanf("%d",&r);
       
        s = 4*(long long)r * r;
        printf("Case %d: %lld",tc,s);
        puts(".25");
    }
   
    return 0;
}

INVCNT

INVCNT

#include <stdio.h> 

#define sz 500000 
#define inf 1000000000 
long a[sz+2],L[sz+2],R[sz+2]; 
long long cnt;

void merge(long p,long q,long r){ 
 long i,j,k,ind1,ind2; 

 for(i = p,ind1 = 1;i <= q;i++){ 
  L[ind1++] = a[i]; 
 } 
 L[ind1] = inf; 

 for(i = q+1,ind2 = 1;i <= r;i++){ 
  R[ind2++] = a[i]; 
 } 
 R[ind2] = inf; 

 i = j = 1; 

 for(k = p;k <= r;k++){ 
  if(L[i] > R[j]){ 
   cnt += ind1 - i; 
   a[k] = R[j]; 
   j++; 
  } 
  else{ 
   a[k] = L[i]; 
   i++; 
  } 
 } 
} 

void mergeSort(long p,long r){ 
 if(p < r){ 
  long q = (p+r)/2; 
  mergeSort(p,q); 
  mergeSort(q+1,r); 
  merge(p,q,r); 
 } 
} 

int main(){ 
 long i,n,t;

 scanf("%ld",&t);
 while( t-- ){
  scanf("%ld",&n);
  for(i = 1;i <= n; i++){ 
   scanf("%ld",&a[i]); 
  } 
  cnt = 0; 
  mergeSort(1,n); 
  printf("%lld\n",cnt); 
 } 

 return 0; 
}

Spoj problem Sphere in a tetrahedron

TETRA

#include<stdio.h>
#include<math.h>
double area(double ,double ,double );
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
        double u,v,w,U,V,W;
        scanf("%lf %lf %lf %lf %lf %lf",&u,&v,&w,&W,&V,&U);
        //scanf("%f %f %f %f %f %f",&u,&U,&v,&V,&w,&W);
        double vol;
        double S=0;
        S+=area(u,V,w);
        S+=area(W,u,v);
        S+=area(W,V,U);
        S+=area(U,v,w);
      
        vol=sqrt(4*u*u*v*v*w*w- u*u*(v*v+w*w - U*U)*(v*v+w*w-U*U) - v*v*(w*w+u*u - V*V)*(w*w+u*u-V*V) - w*w*(u*u + v*v - W*W)*(u*u+v*v-W*W) + (v*v +w*w - U*U)*(w*w+u*u- V*V)*(u*u+v*v - W*W))/12;
        printf("%.4lf\n",vol*3.0/S);
        }
        return 0;
}
double area(double a1,double a2,double a3)
{
        double s=(a1+a2+a3)/2.0;
        return sqrt(s*(s-a1)*(s-a2)*(s-a3));
}

spoj problem help tohu

TOHU

#include<iostream>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
double ans;
ans = (3.0/4.0) + (1.0/(2*(n+2)))-(1.0/(2*(n+1)));
printf("%.11f\n",ans);
}
return 0;
}

spoj problem will it ever stop(WILLITST)

WILLITST

#include<iostream>
using namespace std;
int main()
{
long long N;
while(scanf("%lld",&N)!=EOF)
{if((N&(N-1))==0)// check whether it is a power of 2
printf("TAK\n");
else
printf("NIE\n");
}
return(0);
}

Spoj Problem Histogram(HISTOGRA)

HISTOGRA

#include <iostream>
using namespace std;
void max( long long int &a, long long int b) { if(a<b) a=b; }
long long int res;
#define MAX 100005
long long int V[MAX]; int N;
int l1[MAX];
int l2[MAX];

int fn(int *l)
{
int s[MAX]; int st=0;
V[0]=-1;
s[0]=0;
for(int i=1;i<=N;i++){
while( V[s[st]] >= V[i] ){
st--;
}
l[i] = s[st];
st++;
s[st]=i;
}
}
int main()
{
long long int w,h;
while(1){
cin>>N;
if(N==0) break;
for(int i=1;i<=N;i++) cin >> V[i];
res=0;
fn(l1);
for(int i=1,j=N,k;i<j;i++,j--) {
k=V[i];
V[i]=V[j];
V[j]=k;
}
fn(l2);
for(int i=1;i<=N;i++)
l1[i]=N+1-l1[i];
res=0;
for(int i=1;i<=N;i++)
{
w=l1[N+1-i]-1-l2[i];
h=V[i];
max(res, w*h);
}
cout<<res<<endl;   
}
return 0;
}

Spoj problem Fashion Show(FASHION)

FASHION

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int t,i,n,ans;
int x[1001],y[1001];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d ",&x[i]);
}
for(i=0;i<n;i++)
{
scanf("%d ",&y[i]);
}
 sort(x, x + n);
 sort(y, y + n);
ans=0;
for(i=0;i<n;i++)
{
ans=ans+x[i]*y[i];
}

printf("%d\n",ans);
}
return(0);
}

Spoj problem Behive Number(BEENUMS)

BEENUMS

#include<stdio.h>
int main()
{
        int a,d,k,i;
        scanf("%d",&a);
        while(a!=-1)
        {
        if((a-1)%6==0)
        {
        for(i=0;i<=a/6;i++)
        {
        if(3*i*(i+1)+1==a)
        {
        printf("Y\n");
        break;
        }
}
        if(i==(a/6)+1){
        printf("N\n");
        }
        }
        else{
        printf("N\n");
        }
        scanf("%d",&a);
        }
        return 0;
}    

spoj solution of GCD2

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

Spoj solution of Julka(JULKA)

JULKA

#include <stdio.h>
#include <string.h>

#define MAX 111

char klaudia[MAX], natalia[MAX], total[MAX], diff[MAX];

void calc()
{
    int len1 = strlen(total);
    int len2 = strlen(diff);
    int a, b, c, i, j, k, f;
    char temp[MAX];

    for(i=len1-1, j=len2-1, k=c=0; i>=0 || j>=0 || c; i--, j--, k++)
    {
        a = i>=0? total[i]-'0' : 0;
        b = j>=0? diff[j]-'0' : 0;
        temp[k] = (a+b+c)%10 + '0';
        c = (a+b+c)/10;
    }
    temp[k] = 0;

    strcpy(klaudia,"0");
    for(i=k-1, j=a=f=0; i>=0; i--)
    {
        b = (a*10 + temp[i]-'0') / 2;
        a = (a*10 + temp[i]-'0') % 2;
        if(b) f = 1;
        if(f) klaudia[j++] = b+'0';
    }
    if(!j) j++;
    klaudia[j] = 0;

    for(i=len1-1, j=len2-1, k=c=0; i>=0; i--, j--, k++)
    {
        a = total[i]-'0';
        b = j>=0? diff[j]-'0' : 0;
        if(a < b+c)
        {
            temp[k] = (10+a-b-c) + '0';
            c = 1;
        }
        else
        {
            temp[k] = a-b-c + '0';
            c = 0;
        }
    }
    temp[k] = 0;

        strcpy(natalia,"0");
        for(i=k-1, j=a=f=0; i>=0; i--)
        {
                b = (a*10 + temp[i]-'0') / 2;
                a = (a*10 + temp[i]-'0') % 2;
                if(b) f = 1;
                if(f) natalia[j++] = b+'0';
        }
        if(!j) j++;
        natalia[j] = 0;
}

int main()
{
    while(scanf("%s %s", total, diff)==2)
    {
        calc();
        printf("%s\n%s\n", klaudia, natalia);
    }
    return 0;
}

Spoj solution of Edit Distance Again(EDIT)

EDIT


#include<iostream>
#include<string.h>
int main()
{
    char str[1005];
    int len,i,count1,a,count2;
    while(scanf("%s",str)!=EOF)
    {
        len=strlen(str);
        int arr1[len];
        int arr2[len];
        int arr3[len];
        count1=0,count2=0;
        if(len==1)
            printf("0\n");
        else
        {
            for(i=0;i<len;i++)
            {
                a=str[i];
               // printf("%d ",a);
                if(a>=65&&a<=90)
                    arr1[i]=1;
                else
                    arr1[i]=0;
            }

            a=str[0];
            if(a>=65&&a<=90){
                arr2[0]=1;
                arr3[0]=0;
            }
            else{
                arr2[0]=0;
                arr3[0]=1;
            }
            for(i=1;i<len;i++)
            {
                if(arr2[i-1]==0)
                {
                    arr2[i]=1;
                    arr3[i]=0;
                }
                else{
                    arr2[i]=0;
                    arr3[i]=1;
                }
            }
          
            for(i=0;i<len;i++)
            {
                if(arr1[i]!=arr2[i])
                    count1+=1;
                if(arr1[i]!=arr3[i])
                    count2+=1;
            }
            printf("%d\n",(count1<count2)?count1:count2);
        }
    }
    return 0;
}

Spoj problem Counting triangle

TRICOUNT

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 

int main()
{
  int i,j,k;
  long long  int T,N;
  long long int result;
  
  scanf("%lld",&T);
  while(T--)
  {
     scanf("%lld",&N);
     result=(N*(N+2)*(2*N+1))/8;
     printf("%lld\n",result);
  }

return 0;
}

Spoj problem SUM1

SUM1

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n;
        scanf("%lld",&n);

        long long a,b,c;

        if(n%3)     a=n/3;
        else
        a=(n-1)/3;

        if(n%5)     b=n/5;
        else
        b=(n-1)/5;

        if(n%15)    c=n/15;
        else
        c=(n-1)/15;

        a=(3*a*(a+1))/2;
        b=(5*b*(b+1))/2;
        c=(15*c*(c+1))/2;

        printf("%lld\n",(a+b)-c);
    }

    return 0;
}

Length fact spoj problem

LENGFACT

#include <stdio.h>
#include <math.h>

long long solve(long long n){
    if(n==0 || n==1) return 1;
    if(n <= 10) return (long long)log10(tgamma(n+1)) + 1;
    return (long long)((double)n*log10((double)n/M_E) + 0.5*log10(2*M_PI*n)) + 1;
}

int main(){
    long long n;
    int T;
    for(scanf("%d",&T);T--;){
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
    return 0;
}