Spoj Problem solutions: 2013

AMR11E

AMR11E spoj solution
#include<iostream>

#define N 3000

#include<cmath>

#include<cstdio>

using namespace std;

int prime[N+1];

void sieve(){

    prime[0]=1;

    prime[1]=1;

    for(long long i=2;i<=N;i++){

        if(!prime[i]){

                        prime[i]=i;

            for(long long j=i;j*i<=N;j++){

                prime[j*i]=i;

            }

        }

    }

}

int primeFactorize(int n){

    int ct=0,flag=0;
    for( ; n > 1 ; ){

        int p = prime[n] , e = 0 ;

        for( ; n % p == 0 ; n /= p , e++ ) ;

       ct++;
    if(ct==3){flag=1;break;}
    }
    return flag;

}

int main()

{



    sieve();

   int t;

   scanf("%d",&t);
    int tp[1000],ct=0;

   for(int i=30;i<3000;i++)
    {
        if(primeFactorize(i))tp[ct++]=i;
        if(ct==1000)break;

    }
while(t--)

   {

    int n;

    scanf("%d",&n);
    printf("%d\n",tp[n-1]);

   }



   return 0;

}

AMR10G

AMR10G

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector<int> nn,dm;
int data;
for(int i=0;i<n;i++)
{
cin>>data;
nn.push_back(data);
}
sort(nn.begin(),nn.end());

int j;
for(j=0;j<=(n-k);j++)
dm.push_back(nn[j+k-1]-nn[j]);

sort(dm.begin(),dm.end());

cout<<dm.front()<<endl;
}
return 0;

}

ALLIZWEL

ALLIZWEL

#include <iostream>

#include <cstring>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

char str[]="ALLIZZWELL";

int v[105][105];

int n,m;

vector<string> inp;

int fn(int r, int c, int l)

{

if(l==10)

return true;

v[r][c]=1;

for(int i=-1;i<=1;i++)

for(int j=-1;j<=1;j++)

{

int r1=r+i, c1=c+j;

if((i==0&&j==0)||r1<0||r1>=n||c1<0||c1>=m||inp[r1][c1]!=str[l])

continue;

if(v[r1][c1])

continue;

if( fn(r1,c1,l+1) ){

v[r][c]=0;

return true;

}

}

v[r][c]=0;

return false;

}

int main()

{

int tc;

cin >> tc;

while(tc--){

inp.clear();

cin>>n>>m;

for(int i=0;i<n;i++ ){

string a;

cin>>a;

inp.push_back(a);

}

bool f=false;

for(int i=0;i<n;i++)

for(int j=0;j<m;j++)

if(inp[i][j]=='A' && fn(i,j,1)){

f=true; break;

}

if(f)

cout<<"YES"<<endl;

else

cout<<"NO"<<endl;

}

return 0;

}

ADV04I

ADV04I

#include<iostream>
#include<cstdio>
#include<vector>
#include<list>
#include<string>
#include<map>
#include<algorithm>
#include<complex>
#define fn(i,j,n) for(int i=j;i<n;i++)
#define rn(i,n) fn(i,0,n)
using namespace std;
int main()
{
long long int a,b,i;
a = b = 1;
long long int c;
long long int arr[76];
arr[0]=1;
fn(i,1,75)
    {
    c = a+b;
    arr[i] = c    ;
    a = b;
    b = c;
    }
vector<long long int> fib(arr,arr+76);
int t;
cin>>t;
long long int number;
while(t--)
{
    cin>>number;
    long long int res = 0,num1,num2;
    vector<long long int>::iterator it,kn;
    it = lower_bound(fib.begin(),fib.end(),number);
    kn = it;
    if(*it == number)
        it++;
    num1=*it;
    it--;
    num2=*it;

    res = res + num1;
    number = number - num2;

    while(number>0)
    {
        it = lower_bound(fib.begin(),kn,number);
        kn=it;
        if(*it==number)
            it++;
        num1=*it;
        it--;
        num2=*it;
        res = res + num1;
        number = number - num2;

    }
    cout<<res<<endl;
}
return 0;
}

ADV04J

ADV04J
#include<iostream>
using namespace std;

int main()
{
int t;
cin>>t;
long long int a;
while(t--)
{
cin>>a;
int res=0;
while(a>0)
{
if(a==2)
{ res+=2 ;
break;
}

if(a%2==0)
a/=2;
else
a = (a/2)+1;
res++;
}
cout<<res<<endl;
}
return 0;
}

ANARC05I

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

int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
       long long int a3,a3l,s,i,a,d,len;

      long double n,sq,diff;
      scanf("%lld",&a3);
      scanf("%lld",&a3l);
      scanf("%lld",&s);

      sq=sqrtl(((5.0*a3l+7.0*a3+2.0*s)*(5.0*a3l+7.0*a3+2.0*s))-(48.0*(a3l+a3)*s));
      n=((5.0*a3l+7.0*a3+2.0*s)+sq)/(2.0*(a3l+a3));

      len=llrintl(n);
      printf("%lld\n",len);

      diff=(a3l-a3)/(len-6.0);
      d=llrintl(diff);

      a=(a3-(2*d));





      for(i=0;i<len;i++)
       {
                       printf("%lld ",a+i*d);
       }
        printf("\n");


       }

     return 0;
}

AMZSEQ

AMZSEQ

#include<iostream>
using namespace std;
typedef long long int int64;
int main()
{
int64 arr[10000];
arr[1] = 3;
arr[2] = 7;
int i = 2;
while(arr[i]<1e10)
{
arr[i+1] = 2*arr[i] + arr[i-1];
i++;
}
int n;
cin>>n;
cout<<arr[n]<<endl;
}

AMR11H

AMR11H

#include<iostream>
using namespace std;
const int MAX=1000000007;
int power(int n,int m)
{
    int i,result=1;
    for(i=0;i<m;i++) result=result*n%MAX;
    return result;
}

int main()
{
int min_count,max_count,substr,min,max,a,b,i,j,t,n,temp;
int pos_min[100000],pos_max[100000];
long long int subseq;
cin>>t;
while(t--)
{
    min=100001;max=0;min_count=max_count=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&temp);
        if(min>temp){min=temp;min_count=1;pos_min[min_count-1]=i;}
        else if(min==temp) {min_count++;pos_min[min_count-1]=i;}

        if(max<temp){max=temp;max_count=1;pos_max[max_count-1]=i;}
        else if(max==temp) {max_count++;pos_max[max_count-1]=i;}
    }
    if(min==max) subseq=power(2,n)-1;//(2^N-1)
    else subseq=(long long)(power(2,min_count)-1)*(power(2,max_count)-1)%MAX*power(2,n-min_count-max_count)%MAX;

    if(pos_min[min_count-1]<pos_max[max_count-1]) temp=pos_min[min_count-1];
    else temp=pos_max[max_count-1];

    for(substr=a=b=i=0;i<=temp;i++)
    {
        while(pos_min[a]<i)a++;
        j=pos_min[a];
        while(pos_max[b]<i)b++;
        if(pos_max[b]>j) j=pos_max[b];
        substr=(substr+n-j)%MAX;
}
        printf("%d %lld\n",substr,subseq);
}
return 0;
}

AMR11E

AMR11E

#include<iostream>

#define N 3000

#include<cmath>

#include<cstdio>

using namespace std;

int prime[N+1];

void sieve(){

    prime[0]=1;

    prime[1]=1;

    for(long long i=2;i<=N;i++){

        if(!prime[i]){

                        prime[i]=i;

            for(long long j=i;j*i<=N;j++){

                prime[j*i]=i;

            }

        }

    }

}

int primeFactorize(int n){

    int ct=0,flag=0;
    for( ; n > 1 ; ){

        int p = prime[n] , e = 0 ;

        for( ; n % p == 0 ; n /= p , e++ ) ;

       ct++;
    if(ct==3){flag=1;break;}
    }
    return flag;

}

int main()

{



    sieve();

   int t;

   scanf("%d",&t);
    int tp[1000],ct=0;

   for(int i=30;i<3000;i++)
    {
        if(primeFactorize(i))tp[ct++]=i;
        if(ct==1000)break;

    }
while(t--)

   {

    int n;

    scanf("%d",&n);
    printf("%d\n",tp[n-1]);

   }
return 0;

}

AMR10G

ALIEN

ALIEN

#include<iostream>
#include<cstdio>
using namespace std;
main()
{
int t;
cin>>t;
while(t--)
{
    int i,n,m,min=100000000,j=0,sum=0;scanf("%d%d",&n,&m);int arr[n];
    for(i=0;i<n;i++) scanf("%d",&arr[i]);
    int ct=0;
    int hld=0;
    for(i=0;i<n;i++)
    {
      sum+=arr[i];ct++;for(;sum>m;) {sum-=arr[j++];ct--;}
       if((min>sum)&&(ct==hld)){min=sum;}//if(max==m) break;
       else if(ct>hld){min=sum;hld=ct;}
    }
    printf("%d %d\n",min,hld);

}

return 0;
}

ALICESIE

ALICESIE

#include<iostream>
using namespace std;
int main()

{

int t;
cin>>t;
int a;
while(t--)
{
cin>>a;
cout<<((a%2==0)?a/2:(a/2+1))<<endl;
}
return 0;
}

AE00

AE00
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int a,d;
    long int count=0;
    float b,c;
    cin>>a;
    b=a;
    c=sqrt(b);
    d=c;
    for(int i=1;i<=d;i++)
    count=count+((a/i)-(d-i));

    cout<<count<<endl;

    return 0;

    }

ADV04L

ADV04L

#include<iostream>
#include<cstdio>
#include<vector>
#include<list>
#include<string>
#include<map>
#include<algorithm>
#include<complex>
#define fn(i,j,n) for(int i=j;i<n;i++)
#define rn(i,n) fn(i,0,n)
using namespace std;
int main()
{
long long int a,b,i;
a = b = 1;
long long int c;
long long int arr[76];
arr[0]=1;
fn(i,1,75)
    {
    c = a+b;
    arr[i] = c    ;
    a = b;
    b = c;
    }
vector<long long int> fib(arr,arr+76);
int t;
cin>>t;
long long int number;
while(t--)
{
    cin>>number;
    long long int res = 0,num1,num2;
    vector<long long int>::iterator it,kn;
    it = lower_bound(fib.begin(),fib.end(),number);
    kn = it;
    if(*it == number)
        it++;
    num1=*it;
    it--;
    num2=*it;
    //cout<<num1<<" "<<num2<<endl;
    res = res + num1;
    number = number - num2;
    //cout<<number<<endl;
    while(number>0)
    {
        it = lower_bound(fib.begin(),kn,number);
        kn=it;
        if(*it==number)
            it++;
        num1=*it;
        it--;
        num2=*it;
        res = res + num1;
        number = number - num2;
        //cout<<num1<<" "<<num2<<endl;
        //cout<<number<<endl;
    }
    cout<<res<<endl;
}
return 0;
}

ADV04J

ADV04J

#include<iostream>
using namespace std;

int main()
{
int t;
cin>>t;
long long int a;
while(t--)
{
cin>>a;
int res=0;
while(a>0)
{
if(a==2)
{ res+=2 ;
break;
}

if(a%2==0)
a/=2;
else
a = (a/2)+1;
res++;
}
cout<<res<<endl;
}
return 0;
}

ADDREV

ADDREV

#include<iostream>

int reverse(int a)
{
       int b[10000];int j=0;
    int term=0,rev=0;
    int multi;
    while(a>0)
    {

              b[j]=a%10;
              j++;
              a=a/10;
              }
              for(int x=j;x>0;x--)
              {
                  multi=1;
                  for(int y=0;y<(x-1);y++)
                  multi=multi*10;
                  term=b[j-x]*multi;
                      rev=rev+term;
                      }
    return rev;
    }

using namespace std;

int main()

{
int a,b,c;
int rev1,rev2,rev3,sum;
cin>>a;
for(int i=0;i<a;i++)
{
cin>>b>>c;
rev1=reverse(b);
rev2=reverse(c);
sum=rev1+rev2;
rev3=reverse(sum);
cout<<rev3<<endl;
}

return 0;

}

ACPC11B

ACPC11B

#include<iostream>
using namespace std;
void sort(long long int arr[],int a)
{
    long long int temp;
    for(int i=0;i<a;i++)
        for(int j=1;j<a-i;j++)
        {
            if(arr[j]>arr[j-1])
            {
                temp =arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
}

int main()
{

    int t;
    cin>>t;
    long long int a,b;
    while(t--)
    {

        cin>>a;
        long long int arra[a];
        for(int i=0;i<a;i++)
        {
            cin>>arra[i];
        }
        cin>>b;
        long long int arrb[b];
        for(int i=0;i<b;i++)
        {
            cin>>arrb[i];
        }
        sort(arra,a);
        sort(arrb,b);
        long long int min=1000000;
        int ct1=0,ct2=0;
        while((ct1<a)&&(ct2<b))
        {


            while((arra[ct1]>=arrb[ct2])&&(ct1<a))
                {

                    if((arra[ct1]-arrb[ct2])<min){min = (arra[ct1]-arrb[ct2]);}
                    ct1++;
                }
            while((arra[ct1]<arrb[ct2])&&(ct2<b))
                {

                    if((arrb[ct2]-arra[ct1])<min){min = (arrb[ct2]-arra[ct1]);}
                    ct2++;
                }


        }

        cout<<min<<endl;
    }

return 0;
}

ACPC10D

ACPC10D

#include<iostream>
#include<cmath>
using namespace std;

int min(int a,int b)
{
    if(a<b)
        return a;
    else
        return b;

}

int main()
{
    int t;cin>>t;int count=0;
    while(t!=0)
    {
        count++;
        int arr[t][3];
        for(int j=0;j<t;j++)
            for(int x=0;x<3;x++)
                cin>>arr[j][x];

    arr[0][2]+=arr[0][1];
arr[1][0]+=arr[0][1];
arr[1][1]+=min(arr[0][1],min(arr[1][0],arr[0][2]));
arr[1][2]+=min(arr[0][1],min(arr[1][1],arr[0][2]));

         for(int j=2;j<t;j++)
        {
            arr[j][0] = arr[j][0] + min(arr[j-1][0],arr[j-1][1]);
            arr[j][1] = arr[j][1] + min(arr[j][0],min(arr[j-1][0],min(arr[j-1][1],arr[j-1][2])));
            arr[j][2] = arr[j][2] + min(arr[j][1],min(arr[j-1][1],arr[j-1][2]));
             }
            int lm = arr[t-1][1];
        cout<<count<<". "<<lm<<endl;
        cin>>t;
    }

return 0;
}

ACPC10A

ACPC10A

#include<iostream>
using namespace std;

int main()
{
    long int a,b,c;
    cin>>a>>b>>c;

    while((a!=0)||(b!=0)||(c!=0))
    {
    if((b-a)==(c-b))
    cout<<"AP "<<(c+(b-a))<<endl;
    else if((b/a)==(c/b))
    cout<<"GP "<<(c*(b/a))<<endl;
                                 cin>>a>>b>>c;
                                 }
    return 0;


    }

ABSYS

ABSYS

#include<iostream>
#include<cstring>
#include<cstdlib>

using namespace std;

int main()
{
    int t;
    char str1[100],str2[100],opr[2],opr1[2],str5[100];

    cin>>t;

    for(int i=0;i<t;i++)
    {
    cin>>str1>>opr>>str2>>opr1>>str5;

        if((strchr(str1,'m'))!=NULL)

        {
                           int y=atoi(str2);
                           int z=atoi(str5);
                           int l=z-y;

                         cout<<l<<" + "<<y<<" = "<<z<<endl;
                                 }
           else if ((strchr(str2,'m'))!=NULL)
           {

                           int y=atoi(str1);
                           int z=atoi(str5);
                           int l=z-y;
                          cout<<y<<" + "<<l<<" = "<<z<<endl;

          }
            else if ((strchr(str5,'m'))!=NULL)
            {
                           int y=atoi(str1);
                           int z=atoi(str2);
                           int l=z+y;

                           cout<<y<<" + "<<z<<" = "<<l<<endl;
                 }
            }
    return 0;

    }

ABA12D

ABA12D

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

int main()
{
int arr[]={2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, 17161, 27889, 28561, 29929, 65536, 83521, 85849, 146689, 262144, 279841, 458329, 491401, 531441, 552049, 579121, 597529, 683929, 703921, 707281, 734449, 829921,1190281 };

cin>>t;
int a,b;
while(t--)
{
         cin>>a>>b;
         int a1 = 0,a2=0;
         while(arr[a1++]<a);
         while(arr[a2++]<b);
         cout<<a2-a1<<endl;
}
return 0;
}

ABSYS

ABCD1

ABCD1

#include<stdio.h>
int main()
{
int arr[]={2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, 17161, 27889, 28561, 29929, 65536, 83521, 85849, 146689, 262144, 279841, 458329, 491401, 531441, 552049, 579121, 597529, 683929, 703921, 707281, 734449, 829921,1190281 };
int t;
scanf("%d",&t);
int a,b;
while(t--)
{

scanf("%d%d",&a,&b);
         int a1 = 0,a2=0;
         while(arr[a1++]<a);
         while(arr[a2++]<b);
         printf("%d\n",a2-a1);
}
return 0;
}

ABCD

ABCD

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int main()
{

          int n;
          cin>>n;
          string name;
          cin>>name;
          char ans[2*n+1];int ct = 0;
          for(int i=0;i<2*n;i++)
          {
                    int yy[4] = {0};
                    yy[name[i]-'A']++;
                    i++;
                    yy[name[i]-'A']++;
                    int wait;int flag = 0;
                    for(int j=0;j<4;j++)
                    {
                              if(yy[j]==0 && i==1)
                              {
                                        cout<<char('A'+j);
                                        ans[ct++] = 'A'+j;
                              }
                              else if(yy[j]==0)
                              {
                                        if(ans[ct-1]==('A'+j) && flag==0){flag = 1;wait = j;goto ny;}
                                        if(flag==0)
                                        {
                                                  cout<<char('A'+j);
                                                  ans[ct++] = 'A'+j;
                                        }
                                        else
                                             {     cout<<char('A'+j)<<char('A'+wait);
                                                  ans[ct++] = 'A'+j;
                                                  ans[ct++] = 'A'+wait;
                                           }
                                           ny:;
                              }
                    }
                   // cout<<endl;
          }
          cout<<endl;
          //system("pause");
          return 0;
}

SILVER

SILVER

#include<iostream.h>
#include<cmath>
main()
{
int t,res;
cin>>t;
while(t!=0)
{
    res=0;
    int m=0,r=0;
while(m<t)
{
m+=pow(2,r++);
}
cout<<r-1<<endl;
cin>>t;
}

}

MAYA

MAYA

#include<stdio.h>
int main()
{
long long int result=0;
char temp;
int n,t;
int count;
scanf("%d%c",&n,&temp);
while(n!=0)
{
result=0;
t=n;
while(t>0)
{
scanf("%c",&temp);
count=0;
while(temp!='\n')
{
if(temp=='S')count+=0;
else if(temp=='.')count+=1;
else if(temp=='-')count+=5;
scanf("%c",&temp);
}
if(t==1)
result+=count;
else if(t==2)result+=count*20;
else if(t==3)result+=count*360;
else if(t==4)result+=count*7200;
else if(t==5)result+=count*144000;
else if(t==6)result+=count*2880000;
else if(t==7)result+=count*57600000;
t--;
}
printf("%lld\n",result);
scanf("%d%c",&n,&temp);
}
return 0;
}

BILLIARD

BILLIARD

#include<iostream.h>
#include<cmath>
main()
{
double a,b,s,m,n;
double vx,vy,pi=2*acos(0);
cin>>a>>b>>s>>m>>n;
while(a!=0)
{
vx=m*a/s;
vy = n*b/s;
printf("%.2lf %.2lf\n",atan(vy/vx)*180/pi,sqrt(vx*vx+vy*vy));
cin>>a>>b>>s>>m>>n;
} }

TAP2013G

TAP2013G
#include <iostream>
#include<algorithm>
using namespace std;

int main() {
    int s,count=0;
    cin>>s;
    int n[100001],q[100001];
    for(int i=0;i<s;i++)
    {
        cin>>q[i];
    }
    for(int i=0;i<s;i++)
    {
        cin>>n[i];
    }
    sort(q,q+s);
    sort(n,n+s);
    for(int i=0,j=0;i<s&&j<s;)
    {
        if(q[i]<n[j])
        {
            count++;
            i++;
            j++;
        }
        else if(q[i]==n[j])
        {
            j++;
        }
        else
        j++;

    }
    cout<<count<<endl;

    return 0;
}
simple and easy problems , u only need to give victory any how to alogonia army.

AP2

AP2

#include<iostream>
using namespace std;

int main()
{
    int t;
    cin>>t;
    long long int a,b,s;
    while(t--)
    {
              cin>>a>>b>>s;
             long long int n = (s*2)/(a+b);
             long long int d = (b-a)/(n-5);
             long long int f = a-(2*d);
              cout<<n<<endl;
              for(long long int i=0;i<n;i++)
               cout<<f+(i*d)<<" ";
              cout<<endl;
    }

    return 0;
}

AP3

AP3

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

int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
       long long int a3,a3l,s,i,a,d,len;

      long double n,sq,diff;
      scanf("%lld",&a3);
      scanf("%lld",&a3l);
      scanf("%lld",&s);

      sq=sqrtl(((5.0*a3l+7.0*a3+2.0*s)*(5.0*a3l+7.0*a3+2.0*s))-(48.0*(a3l+a3)*s));
      n=((5.0*a3l+7.0*a3+2.0*s)+sq)/(2.0*(a3l+a3));

      len=llrintl(n);
      printf("%lld\n",len);

      diff=(a3l-a3)/(len-6.0);
      d=llrintl(diff);

      a=(a3-(2*d));





      for(i=0;i<len;i++)
       {
                       printf("%lld ",a+i*d);
       }
        printf("\n");


       }

     return 0;
}

ACPC11B

ACPC10A

ACPC10A

#include<iostream>
using namespace std;
int main()
{
long int a,b,c;
while(1)
{
cin>>a>>b>>c;
if(a==0&&b==0&&c==0)
{break;}
else if(b-a==c-b)
{
cout<<"AP"<<" "<<(b-a)+c<<endl;
}
else if(b/a==c/b)
{
cout<<"GP"<<" "<<(b/a)*c<<endl;
}
}
return 0;
}

LENGFACT

LENGFACT

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int t;
cin>>t;
double n;
double pi = 2*acos(0);
long long int len,l;

while(t-->0)
{
        cin>>n;
        if(n==0.00||n==1.00)l=1;

        else{
        l=(((log(2.00*pi*n)/2.00)+(n*(log(n)-1.00)))/log(10.0))+1;
        }


        cout<<l<<endl;
}
return 0;
}

PIR

PIR

#include <stdio.h>

#include <math.h>

main()

{

int t;

scanf("%d",&t);

while (t > 0) {

int edges[6];

for (int i =0; i<6; ++i) {
scanf("%d", (edges+i));

}

double u = edges[0];

double U = edges[5];

double v = edges[3];

double V = edges[2];

double w = edges[4];

double W = edges[1];

double uu = (v*v) + (w*w) - (U*U);

double vv = (w*w) + (u*u) - (V*V);

double ww = (u*u) + (v*v) - (W*W);

double vol = (4*u*u*v*v*w*w)-(u*u*uu*uu)-(v*v*vv*vv)-(w*w*ww*ww)+(uu*vv*ww);

double volume = (sqrt(vol)) / 12;

printf("%.4lf\n", volume);

t--;

}

return 0;
}

UCV2013J

UCV2013J

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

int main()
{
    int n, c, s, t, i, l;
    scanf("%d", &n);
    while (n!=0)
    {
        s=1;
        while (s-1<n) {

            s*=2;
        }
        s/=2;
        s--;
        s-=(s/2-(n-s-1)/2);
        for (i=0; i<s; i++) {
            scanf("%d", &c);
        }
        t=0;
        for (i=s; i<n; i++) {
            scanf("%d", &c);
            t+=c;
        }
        printf("%d\n",t);
        scanf("%d", &n);
    }
    return 0;
}

UCV2013I

UCV2013I

#include <stdio.h>
#include <math.h>
int main()
{
double r;
int l,n;
scanf("%d%d",&l,&n);
while(n!=0 && l!=0)
{
r = 2*l/(2*sin(acos(-1)/(n*2)));

printf("%.2lf\n",r);
scanf("%d%d",&l,&n);
}
return 0;
}

UCV2013C

UCV2013C

#include<iostream>
using namespace std;

int main()
{
unsigned long long d,f,b,m,p,p1,p2;
while(true)
{
cin>>d>>f>>b>>m;
if(d==0||f==0||b==0||m==0)
break;
p=f*(f+1)/2 + 1;
p1=p*b;
p2=p1+m;
if(p2>d)
{
cout<<"The firm is trying to bankrupt Farmer Cream by "<<p2-d<<" Bsf."<<endl;
}
else
{
cout<<"Farmer Cream will have "<<d-p1<<" Bsf to spend."<<endl;
}
}
return(0);
}

UCV2013A

UCV2013A

#include<iostream>
#include<stdio.h>
using namespace std;
#define m 1000000007
int main()
{
long long int n, l, a, b;
while (1)
{
a = 1;
b = 0;
scanf("%lld%lld",&n,&l);
if(n == 0 && l == 0) return 0;
for (int i = 1; i < l + 1; i++)
{
a=(n *a)% m;
b=(b+a) % m;
}
printf("%lld\n",b);
}
return(0);

}

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

AP- Complete the series Spoj solution(AP2)

AP2

#include<stdio.h>
#define LL long long
int main()
{
int t;
scanf("%d",&t);
while(t--){
LL a,b,c,i,j;
scanf("%lld%lld%lld",&a,&b,&c);
LL n=(c*2)/(a+b);
LL d=(b-a)/(n-5);
LL m=a-2*d;
printf("%lld\n",n);
for(i=m,j=0;j<n;i+=d,j++){
printf("%lld ",i);
}
printf("\n");
}
return 0;
}

Spoj Problem Candy 3(CANDY3)

CANDY3

#include<iostream>
using namespace std;
int main()
{
int t, n, i;
long long s, a;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
s = 0;
for(i=0;i<n;i++)
{
scanf("%lld",&a);
s += a;
if(s >= n) s %= n;
}
if(s == 0) printf("YES\n");
else printf("NO\n");
}
return 0;
}

Spoj Problem Solution ololo(OLOLO)

OLOLO

#include<iostream>
using namespace std;
int main()
{
    int n,i;
    scanf("%d",&n);
    long long int arr[500001];
    for(i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    long long int a,ans;
    a=arr[0];
    for(i=1;i<n;i++)
    {
        ans=a^arr[i];
        a=ans;
    }
    printf("%lld\n",ans);
    return 0;
}

Spoj Problem solution for Dota Heros(DOTAA)

DOTAA

#include<iostream>
using namespace std;
int main()
{
int t,n,m,d,h;
scanf("%d",&t);

while(t--)
{
int count=0;
scanf("%d %d %d",&n,&m,&d);
while(n--)
{
scanf("%d",&h);
if(h>d)
{
while(h>0)
{
    h=h-d;
    count++;

}
count--;
}
}
if(count<m)
printf("NO\n");
else
printf("YES\n");
}
return(0);
}

Last digit Re Visited(LASTDIG2)

LASTDIG2

#include<stdio.h>
#include<string.h>
int main()
{
char str[1005];
unsigned long long int b,a,ans,len,t;
scanf("%llu",&t);
while(t--){
scanf("%s",str);
scanf("%llu",&b);
len=strlen(str);
a=str[len-1]-'0';
if(b==0&&a!=0) ans=1;
else{
if(a==0){ ans=0; goto end;}
if(a==5) {ans=5; goto end;}
switch(b%4){
case 0: ans=a%2!=0? 1:6;
break;
case 1: ans=a;
break;
case 2: ans=a*a%10;
break;
default : ans=a*a*a%10;
break;
}
}
end :
printf("%llu\n",ans);
}
return 0;
}

problem solution for last digit(LASTDIG)

LASTDIG

#include<stdio.h>
#include<string.h>
int main()
{
char str[1005];
unsigned long long int b,a,ans,len,t;
scanf("%llu",&t);
while(t--){
scanf("%s",str);
scanf("%llu",&b);
len=strlen(str);
a=str[len-1]-'0';
if(b==0&&a!=0) ans=1;
else{
if(a==0){ ans=0; goto end;}
if(a==5) {ans=5; goto end;}
switch(b%4){
case 0: ans=a%2!=0? 1:6;
break;
case 1: ans=a;
break;
case 2: ans=a*a%10;
break;
default : ans=a*a*a%10;
break;
}
}
end :
printf("%llu\n",ans);
}
return 0;
}

Triple fat ladies(EIGHT)

problem link:EIGHT

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

Amusing number spoj problem solution(TSHOW1)

TSHOW1

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main()
{
    int t;
    long long int num,temp,n,i,j,ans,k,rem;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&num);
        temp=0,n=0;
        while(temp<num)

        {
            n=n+1;
            temp=pow(2,n+1)-2;

        }
        temp=pow(2,n)-2;

        ans=num-temp-1;
        char str[100000];
        int k=-1;


        while(ans>0)
        {
            rem=ans%2;
            k=k+1;
            str[k]=rem+'0';
            ans=ans/2;
        }
        j=n-k-1;
        for(i=1;i<=j;i++)
            printf("5");


        for(i=k;i>=0;i--){
            if(str[i]=='0')
                printf("5");
            else
                printf("6");
        }
        printf("\n");
    }
    return 0;
}

manku word spoj solution(MAY99_2)

MAY99_2

#include <cstdio>
#include <cmath>
#include <string>
#include <iostream>
   using namespace std;

int nchar( long long int a)

{
int ctr = 0;
   long long int n = 0;
    while( n < a)
     {
      n += pow(5,++ctr);

       }
        return ctr;
        }

int main()
{
int t;
   scanf("%d",&t);
    string m ="manku";
     long long int n;
      while(t--)
       {
        string s = "";
         scanf("%lld",&n);
          int g = nchar(n);
           for( int i = 0; i < g ;i++)
            {
             int j = n % 5;
              if( j == 0)
               j=5;
                s = m.substr(j-1,1) + s ;
                 if(n%5 ==0)
                 n = n/5 -1;
                  else
                   n = n / 5;
                    }
                    cout <<s<< endl;

                     }
                      return 0;
                       }

Pages