Spoj Problem solutions: December 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;
}

Spoj Problem solutions

Pages

AMR11E

AMR10G

ALLIZWEL

ADV04I

ADV04J

ANARC05I

AMZSEQ

AMR11H

AMR11E

AMR10G

ALIEN

ALICESIE

AE00

ADV04L

ADV04J

ADDREV

ACPC11B

ACPC10D

ACPC10A

ABSYS

ABA12D

Search This Blog

Pages