SPOJ Problem Set (classical) 302. Count on Cantor Problem code: CANTON

//http://www.spoj.com/problems/CANTON/
#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int i,num,sum=0;
        scanf("%d",&num);
        for(i=1;;i++)
        {
            sum+=i;
            if(sum>=num)
                break;
        }
        int temp=num-(sum-i);
        int total=i+1;
        if(i%2==0)
            printf("TERM %d IS %d/%d\n",num,temp,total-temp);
        else
            printf("TERM %d IS %d/%d\n",num,total-temp,temp);
    }
    return 0;
}

SPOJ Problem Set (classical) 1. Life, the Universe, and Everything Problem code: TEST

//http://www.spoj.com/problems/TEST/

#include<stdio.h>
#define monu while ( scanf("%d",&sonu)!=-1 && sonu!=42 && printf("%d\n",sonu))
int main()
{
int sonu;
monu;
return 0;
}

SPOJ Problem Set (classical) 400. To and Fro Problem code: TOANDFRO

//http://www.spoj.com/problems/TOANDFRO/

#include<stdio.h>
#include<string.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t)
    {
        char arr[300];
        scanf("%s",arr);
        int len=strlen(arr)/t;
        char ans[len][t];
        int i,j,k=0;
        for(i=0;i<len;i++)
        {
            if(i%2)
            {
                for(j=t-1;j>=0;j--)
                   ans[i][j]=arr[k++];
            }
            else{
            for(j=0;j<t;j++)
            {
                ans[i][j]=arr[k++];
            }}
        }
        for(i=0;i<t;i++)
        {
            for(j=0;j<len;j++)
                printf("%c",ans[j][i]);
        }
        printf("\n");
        scanf("%d",&t);
    }
    return 0;
}

SPOJ Problem Set (classical) 1724. Counting Triangles Problem code: TRICOUNT

//http://www.spoj.com/problems/TRICOUNT/

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long unsigned num,sum;
        scanf("%llu",&num);
        if(num%2==0)
        sum=(num*(num+2)*((2*num)+1))/8;
        else
        sum=((num*(num+2)*((2*num)+1))-1)/8;
        printf("%llu\n",sum);
    }
    return 0;
}

SPOJ Problem Set (classical) 9948. Will it ever stop Problem code: WILLITST

//http://www.spoj.com/problems/WILLITST/

#include<stdio.h>
#include"string.h"
int main()
{

    long long int x;
    scanf("%lld",&x);
    if(((x != 0) && ((x & (~x + 1)) == x)))    //checks for 2^n
        printf("TAK\n");
    else
        printf("NIE\n");
    return 0;
}

SPOJ Problem Set (classical) 5. The Next Palindrome Problem code: PALIN

//http://www.spoj.com/problems/PALIN/

#include<stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char K[1000002];
int flag;
void find_palin()
{
int len,i,tmp,t,tmp1;
len = strlen(K);
flag = 1;
for(i=0; i<len; i++)
{
if(K[i] != '9')
{
flag = 0;
break;
}
}
if(flag == 1)
{
K[0] = '1';
for(i=1; i<len; i++)
K[i] = '0';
K[len] = '1';
K[len+1] = '\0';
return ;
}
flag = 0;
for(i=0; i<len/2; i++)
{
if(K[i] < K[len-i-1])
flag = -1;
else if(K[i] > K[len-i-1])
flag = 1;
K[len-i-1] = K[i];
}
if(flag == -1 || flag==0)
{
t = 0;
if(len%2 == 0)
tmp1 = len/2-1;
else
tmp1 = len/2;
while(K[tmp1-t] == '9')
{
K[tmp1-t] = '0';
K[len-1-tmp1+t] = '0';
t ++;
}
K[tmp1-t] ++;
K[len-1-tmp1+t] = K[tmp1-t];
}
return ;
}
int main()
{
int t,i;
scanf("%d\n",&t);
for(i=0; i<t; i++)
{
gets(K);
find_palin();
printf("%s\n",K);
}
return 0;
}

SPOJ Problem Set (classical) 379. Ambiguous Permutations Problem code: PERMUT2

//http://www.spoj.com/problems/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;
}

SPOJ Problem Set (classical) 2. Prime Generator Problem code: PRIME1

//http://www.spoj.com/problems/PRIME1/

#include <cstdio>
#include <cmath>
unsigned int numbers[3500], len;
inline bool prime(unsigned int x)
{
unsigned int i, last = sqrt(x);
for (i = 2; i <= last; i++)
{
if (!(x % i))
{
return 0;
}
}
return 1;
}
void generate()
{
for (unsigned int i = 2; i < 32000; i++)
{
if (prime(i))
{
numbers[len++] = i;
}
}
}
inline bool process(unsigned long x)
{
unsigned int i, last = sqrt(x);
for (i = 0; i < len && numbers[i] <= last; i++)
{
if (!(x % numbers[i])) { return 0; }
}
return 1;
}
int main()
{
int tests;
unsigned long begin, end;
generate();
scanf("%d", &tests);
while (tests-- > 0)
{
scanf("%u %u", &begin, &end);
if (begin == 1)
{
begin++;
}
while (begin <= end)
{
if (process(begin))
{
printf("%u\n", begin);
}
begin++;
}
printf("\n");
}
return 0;
}

SPOJ Problem Set (classical) 3410. Feynman Problem code: SAMER08F

//http://www.spoj.com/problems/SAMER08F/

#include<stdio.h>
#define sqr(n) (n*n)
int main()
{
int n,temp=0;
while(1)
{
scanf("%d",&n);
if(n==0){break;}
temp=0;
while(n)
{
temp+=sqr(n);
n--;
}

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

SPOJ Problem Set (classical) 27. Sorting Bank Accounts Problem code: SBANK

//http://www.spoj.com/problems/SBANK/

#include <cassert>//c headers in c++
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>//c++ headers
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

/*START OF TEMPLATE:*/
#define INF 2000000000//::INF
#define VAR(x,a) __typeof(a) x=(a)//::VAR(
#define FE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)//::FE(
#define FOR(i,a,b)   for(int i=(int)(a),_b=(int)(b) ; i < _b;++i)//::FOR(
#define FORR(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)//::FORR(
#define REP(i,n)     FOR(i,0,n)//::REP(
#define ALL(c) (c).begin(),(c).end()//::ALL(
#define SZ(c) (int)(c).size()//::SZ(
#define PB      push_back//::PB
#define PF      push_front//::PF
#define V(x)    vector< x >//::V(
#define VI      V(int)//::VI
#define VVI     V(VI)//::VII
#define VS      V(string)//::VS
#define PI     pair< int,int >//::PI
#define MP      make_pair//::MP
#define pi      3.14159265358979323846//::pi

const double eps=1e-11;//::eps
typedef long long LL;//::LL
typedef unsigned long long ULL;//::ULL
typedef long double LD;//::LD

/* Bitmasking Common Operator Follows */
#define two(X) (1<<(X))//::two(
#define twoL(X) (((LL)1)<<(X))//::twoL(
#define setBit(S,X) (S|=two(X))//::setBit(
#define setBitL(S,X) (S|=twoL(X))//::setBit(
#define contain(S,X) ((S&two(X))>0)//::contain(
#define containL(S,X) ((S&twoL(X))>0)//::containL(
template<class T> inline T lowbit(T n){return (n^(n-1))&n;}//::lowbit(
template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}//::countbit(

template<class T> inline T sqr(T x){return x*x;}//::sqr

/* Numeric Function */
template<class T> inline T gcd(T a,T b)//::gcd(
{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);while (b > 0){a = a % b;a ^= b;b ^= a; a ^= b; } return a;}
template<class T> inline T lcm(T a,T b)//::lcm(
{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
template<class T> inline bool isPrime(T n)//::isPrime(
{if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
template<class T> inline T euclide(T a,T b,T &x,T &y)//::euclide(
{if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;}
if(b<0){T d=euclide(a,-b,x,y);y=-y;return d;}
if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,x,y);T t=x;x=y;y=t-(a/b)*y;return d;}}
template<class T> inline vector<pair<T,int> > factorize(T n)//::factorize(
{vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));}
i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;}
template<class T> inline T eularFunction(T n)//::eularFunction(
{vector<pair<T,int> > R=factorize(n);T r=n;for (int i=0;i<R.size();i++)r=r/R[i].first*(R[i].first-1);return r;}

/* Mathematics Fraction Class */
template<class T> struct Fraction{T a,b;Fraction(T a=0,T b=1);string toString();};//::Fraction
template<class T> Fraction<T>::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<"/"<<b;return sout.str();}
template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}
template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}

/*Matrix Operations*/
const int MaxMatrixSize=40;//::MaxMatrixSize
template<class T> inline void showMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//::showMatrix(
{for(int i=0;i<n;i++){for(int j=0;j<n;j++)cout<<A[i][j];cout<<endl;}}
template<class T> inline T checkMod(T n,T m) {return (n%m+m)%m;}//::checkMod(
template<class T> inline void identityMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//::identityMatrix(
{for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j]=(i==j)?1:0;}
template<class T> inline void addMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//::addMatrix(
{for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}
template<class T> inline void subMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//::subMatrix(
{for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]-B[i][j];}
template<class T> inline void mulMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//::mulMatrix(
{ T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
for(int i=0;i<n;i++) for(int j=0;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=0;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) C[i][j]+=A[i][k]*B[k][j];}
template<class T> inline void addModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//::addModMatrix(
{for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=checkMod(A[i][j]+B[i][j],m);}
template<class T> inline void subModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//::subModMatrix(
{for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=checkMod(A[i][j]-B[i][j],m);}
template<class T> inline T multiplyMod(T a,T b,T m) {return (T)((((LL)(a)*(LL)(b)%(LL)(m))+(LL)(m))%(LL)(m));}//::multiplyMod(
template<class T> inline void mulModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//::mulModMatrix(
{ T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
for(int i=0;i<n;i++) for(int j=0;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=0;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) C[i][j]=(C[i][j]+multiplyMod(A[i][k],B[k][j],m))%m;}
template<class T> inline T powerMod(T p,int e,T m)//::powerMod(
{if(e==0)return 1%m;else if(e%2==0){T t=powerMod(p,e/2,m);return multiplyMod(t,t,m);}else return multiplyMod(powerMod(p,e-1,m),p,m);}

/*Point&Line*/
double dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}//::dist(
double distS(double x1,double y1,double x2,double y2){return sqr(x1-x2)+sqr(y1-y2);}//::distS(
template<class T> T cross(T x0,T y0,T x1,T y1,T x2,T y2){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//::cross(
int crossOper(double x0,double y0,double x1,double y1,double x2,double y2)//::crossOper(
{double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return 0;return (t<0)?-1:1;}
bool isIntersect(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)//::isIntersect(
{return crossOper(x1,y1,x2,y2,x3,y3)*crossOper(x1,y1,x2,y2,x4,y4)<0 && crossOper(x3,y3,x4,y4,x1,y1)*crossOper(x3,y3,x4,y4,x2,y2)<0;}
bool isMiddle(double s,double m,double t){return fabs(s-m)<=eps || fabs(t-m)<=eps || (s<m)!=(t<m);}//::isMiddle(

/* Most Common Coversion */
template<class T> int toInt(T n){int r=0;istringstream ist(n);ist>>r;return r;}//::toInt(
template<class T> long long toLong(T n){istringstream ist(n);long long r;ist>>r;return r;}//::toLL(
template<class T> string toString(T n){stringstream ost;ost<<n;ost.flush();return ost.str();}//::toString(
template<class T> long double toDouble(T n){long double r=0;istringstream sin(n);sin>>r;return r;}//::toDouble(
template<class T> void stoa(string s,int &n,T A[]){n=0;istringstream sin(s);for(T v;sin>>v;A[n++]=v);}//::stoa(
template<class T> void atos(int n,T A[],string &s){ostringstream sout;for(int i=0;i<n;i++){if(i>0)sout<<' ';sout<<A[i];}s=sout.str();}//::atos(
template<class T> void atov(int n,T A[],vector<T> &vi){vi.clear();for (int i=0;i<n;i++) vi.push_back(A[i]);}//::atov(
template<class T> void vtoa(vector<T> vi,int &n,T A[]){n=vi.size();for (int i=0;i<n;i++)A[i]=vi[i];}//::vtoa(
template<class T> void stov(string s,vector<T> &vi){vi.clear();istringstream sin(s);for(T v;sin>>v;vi.push_back(v));}//::stov(
template<class T> void vtos(vector<T> vi,string &s){ostringstream sout;int a=vi.size();for (int i=0;i<a;i++){if(i>0)sout<<' ';sout<<vi[i];}s=sout.str();}//::vtos(

/* Input Output Function */
#define INPUT fread(IBUF, 1, BUFSIZE, stdin);
#define BUFSIZE (1<<26)
char IBUF[BUFSIZE+1], *inputptr=IBUF, OBUF[BUFSIZE+1], *outputptr=OBUF, DIP[20];
#define DIG(a) (((a)>='0')&&((a)<='9'))//::DIG(
#define getChar(t) {t=*inputptr++;}//::getChar(
template<class T>inline bool getInt(T &j) {j=0;int _t;getChar(_t);if(_t==0)return false;char sign;while(!DIG(_t)&&_t!=0){sign=_t;getChar(_t);}while(DIG(_t)){j=10*j+(_t-'0');getChar(_t);}if(sign == '-') j = -j;*inputptr--;return j==0&&_t==0?false:true;}//::getInt(
inline bool getString(char *s) {char _c;getChar(_c);if(_c==0)return false;while(_c==10||_c==32)getChar(_c);while(_c != 10&&_c != 32&&_c!=0){*s++=_c;getChar(_c)}*s=0;inputptr--;return s[0]==0&&_c==0?false:true;}
template<class T> inline void putInt(T x, char n=0) {int y, dig=0;while(x){y=x%10;DIP[dig++]=y+'0';x/=10;}while (dig--) *outputptr++=DIP[dig];n?*outputptr++=n:0;}
template<class T> inline void putString(T *s, char n=0){while(*s)*outputptr++=*s++;n?*outputptr++=n:0;}
#define putLine() {*outputptr++=10;}
#define OUTPUT fputs(OBUF, stdout);

/* Only for Debugging */
#define out(__debug) cout << #__debug<< "=" <<__debug << endl;//::out(
template<class T> void outC(T A)//::outContainer
{cout<<"{"; FE(it,A)cout << *it << " " ;cout<<"}"<<endl;}
template<class T> void outA(T A[],int n)//::outArray
{ cout<<"{"; for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<"}"<<endl;}
template<class T> void outV(vector<T> A,int n=-1)//::outVector
{ if (n<0) n=SZ(A); cout<<"{"; for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<"}"<<endl;}
template<class T> static void split(const string &s, vector<T> &out)//::split(
{istringstream in(s);out.clear();copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));}
/*END TEMPLATE:BY_PANKAJ_CODEGAMBLER*/

int main()
{
// freopen("SBANK.cppin","r",stdin);
INPUT;
int T;
getInt(T);
while(T--){
int n;//scanf("%d", &n);
getInt(n);
map<string, int> res;
char c1[30], c2[30], c3[50], c4[50], c5[50], c6[50];
REP(i, n){
getString(c1);getString(c2);getString(c3);getString(c4);getString(c5);getString(c6);
char s[30];s[0] = 0;
strcat(s, strcat(c1, strcat(c2, strcat(c3, strcat(c4, strcat(c5, c6))))));
// res.insert(MP(s, 0));
res[s]++;
}
FE(i, res){
putString("", i->first[0]);
putString("", i->first[1]);
putString(" ");
FOR(j, 2, 10)putString("", i->first[j]);putString(" ");
REP(j, 4){FOR(k, 10+j*4, 10+(j+1)*4)putString("", i->first[k]);
putString(" ");
}
putInt(i->second, 10);
}
putLine();
}
OUTPUT;
return 0;
}

SPOJ Problem Set (classical) 4. Transform the Expression Problem code: ONP

//http://www.spoj.com/problems/ONP/

# include <stdio.h>

int main()
 {
  unsigned long cases,top=0,i;
  char exp[400],stack[200];
  scanf("%u",&cases);
  while(cases)
   {
      scanf("%s",exp);
      printf("\n");
      for(i=0;exp[i];i++)
       {
        if(exp[i]=='(')
          continue;
        else if(exp[i]==')')
          {
           printf("%c",stack[top]);
           top--;
          }
        else if(exp[i]=='+' || exp[i]=='-' || exp[i]=='*' || exp[i]=='/' || exp[i]=='^')
         {
          top++;
          stack[top]=exp[i];
         }
        else
         {
          printf("%c",exp[i]);
         }
       }    
    cases--;
   }
  return 0;
 }

SPOJ Problem Set (classical) 1112. Number Steps Problem code: NSTEPS

// http://www.spoj.com/problems/NSTEPS/

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,temp,val;
        scanf("%d%d",&x,&y);
        if(x==0||x==1)
        {
            if(x==y)
                printf("%d\n",x);
            else
                printf("No Number\n");
        }
        else
        {
            if(y==x||y==(x-2))
            {
                if(x%2)
                    temp=x-1;
                else
                    temp=x;
                val=((temp-2)/2)*4+1;
                if(x%2)
                {
                    if(y==x)
                        printf("%d\n",val+4);
                    else
                        printf("%d\n",val+2);
                }
                else
                {
                    if(y==x)
                        printf("%d\n",val+3);
                    else
                        printf("%d\n",val+1);
                }
            }
            else
                printf("No Number\n");
        }
    }
    return 0;
}

SPOJ Problem Set (classical) 31. Fast Multiplication Problem code: MUL

// http://www.spoj.com/problems/MUL/

#include <cstdio>
#include <cstring>
#include <complex>
#include <vector>
#include <cmath>

using namespace std;

#define lowbit(x) (((x) ^ (x-1)) & (x))
typedef complex<long double> Complex;

void FFT(vector<Complex> &A, int s){
int n = A.size(), p = 0;

while(n>1){
   p++;
   n >>= 1;
}

n = (1<<p);

vector<Complex> a = A;

for(int i = 0; i < n; ++i){
int rev = 0;
for(int j = 0; j < p; ++j){
rev <<= 1;
rev |= ( (i >> j) & 1 );
}
A[i] = a[rev];
}

Complex w, wn;

for(int i = 1; i <= p; ++i){
int M = 1 << i;
int K = M >> 1;
wn = Complex( cos(s*2.0*M_PI/(double)M), sin(s*2.0*M_PI/(double)M) );
for(int j = 0; j < n; j += M){
w = Complex(1.0, 0.0);
for(int l = j; l < K + j; ++l){
Complex t = w;
t *= A[l + K];
Complex u = A[l];
A[l] += t;
u -= t;
A[l + K] = u;
w *= wn;
}
}
}

if(s==-1){
        for(int i = 0;i<n;++i)
            A[i] /= (double)n;
    }
}

vector<Complex> FFT_Multiply(vector<Complex> &P, vector<Complex> &Q){
    int n = P.size()+Q.size();
    while(n!=lowbit(n)) n += lowbit(n);
   
    P.resize(n,0);
    Q.resize(n,0);
   
    FFT(P,1);
    FFT(Q,1);
   
    vector<Complex> R;
    for(int i=0;i<n;i++) R.push_back(P[i]*Q[i]);
   
    FFT(R,-1);
   
    return R;
}

const long long B = 100000;
const int D = 5;

int main(){
    int n,l1,l2,L;
    char s1[10001],s2[10001];
    vector<Complex> P,Q,ans;
    vector<long long> N;
   
    scanf("%d",&n);
   
    for(int tc = 1;tc<=n;tc++){
        scanf("%s %s",s1,s2);
        l1 = strlen(s1);
        l2 = strlen(s2);
       
        P.clear(); Q.clear();
       
        for(int i = l1-1,val;i>=0;){
            val = 0;
            for(int j = D-1;j>=0;--j) if(i>=j) val = val*10+(s1[i-j]-'0');
            i -= D;
            P.push_back(Complex(val,0));
        }
       
        for(int i = l2-1,val;i>=0;){
            val = 0;
            for(int j = D-1;j>=0;--j) if(i>=j) val = val*10+(s2[i-j]-'0');
            i -= D;
            Q.push_back(Complex(val,0));
        }
       
        ans = FFT_Multiply(P,Q);
        L = ans.size();
       
        N.clear();
        for(int i = 0;i<L;++i) N.push_back((long long)round(real(ans[i])));
       
        for(;L>1 && N[L-1]==0;){
            N.pop_back();
            --L;
        }
       
        for(int i = 0;i<L;++i){
            if(N[i]>=B){
                if(i==L-1){
                    N.push_back(N[i]/B);
                    L++;
                }else N[i+1] += N[i]/B;
                N[i] %= B;
            }
        }
       
        for(int i = L-1;i>=0;--i){
            if(i<L-1){
                int d = 0, aux = N[i];
               
                if(aux>0){
                    while(aux>0){
                        aux /= 10;
                        ++d;
                    }
                }else d = 1;
               
                for(int j = d;j<D;++j) printf("0");
            }
            printf("%lld",N[i]);
        }
        printf("\n");
    }
   
    return 0;
}

SPOJ Problem Set (classical) 3442. The last digit Problem code: LASTDIG

//http://www.spoj.com/problems/LASTDIG/

import java.util.*;
class LASTDIG {
 public static void main(String[] args) {
Scanner input = new Scanner(System.in);
 int cases = input.nextInt();
for (int i=0;i<cases;i++) {
 int base = input.nextInt();
int exponent = input.nextInt();
if (exponent == 0) {
System.out.println(1);
 }
else {
 exponent %= 4;
 if (exponent == 0) {

 exponent = 4;
}
int answer = 1;
 for(int j=0;j<exponent;++j)
{

 answer *= base;
}
System.out.println(answer%10);

}
 }
 }
 }

SPOJ Problem Set (classical) 54. Julka Problem code: JULKA

//http://www.spoj.com/problems/JULKA/

import java.util.*;
import java.math.*;
class julka
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        for(int i=0;i<10;i++)
        {
            BigInteger Apples = new BigInteger(in.next());
            BigInteger more = new BigInteger(in.next());
            BigInteger Klaudia = (Apples.add(more)).divide(new BigInteger("2"));
            BigInteger Natalia = Apples.subtract(Klaudia);
            System.out.println(Klaudia.toString());
            System.out.println(Natalia.toString());
        }
    }
}

SPOJ Problem Set (classical) 13404. The Encrypted Password Problem code: ICPC12C

// http://www.spoj.com/problems/ICPC12C/

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <climits>
#include <ctime>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int cum[26];
int main()
{
 int t;
 scanf("%d ",&t);
 while(t--)
 {
  char s[100009],o[100009];
  scanf("%s",s);
  scanf("%s",o);
  int i=0,a[27],j,flag,k;
  for(i=0;i<26;i++)
   cum[i]=0,a[i]=0;
  i=0;
  while(o[i] != '\0')
  {
   j=o[i] - 97;
   a[j]++;
   i++;
  }
  int size=i;
  i=0;
  while(i<size)
  {
   k=s[i++] -97;
   cum[k]++;
  }
  if(size == strlen(s)){
   flag=1;
   for(i=0;i<26;i++)
    if(cum[i] != a[i])
    {
     flag=0;
     break;
    }
   if(flag)
    printf("YES\n");
   else
    printf("NO\n");
   continue;
  }
  i=size;
  while(s[i]!='\0')
  {
   flag=1;
   k=s[i] - 97;
   cum[k]++;
   k=s[i-size]-97;
   cum[k]--;
   for(j=0;j<26;j++)
    if(cum[j] != a[j])
    {
     flag=0;
     break;
    }
   if(flag)
    break;
   i++;
  }
  if(flag)
   printf("YES\n");
  else
   printf("NO\n");
 }
 return 0;
}

SPOJ Problem Set (classical) 902. Hangover Problem code: HANGOVER

//http://www.spoj.com/problems/HANGOVER/

#include<stdio.h>
int main()
{
    float arr[275];
    int i;
    for(i=0;i<275;i++)     //precomputes 1/i, not really necessary
    {
        arr[i]=1.0/(2.0+i);
    }
    float t;
    scanf("%f",&t);
    while(t)
    {
        float sum=0;
        for(i=0;i<275;i++)
         {
             sum+=arr[i];
             if(sum>=t)
                break;
        }
        printf("%d card(s)\n",i+1);
        scanf("%f",&t);
    }
    return 0;
}

SPOJ Problem Set (classical) 1025. Fashion Shows Problem code: FASHION

//http://www.spoj.com/problems/FASHION/

#include<stdio.h>
#include<algorithm>    //for using sort function
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int i,ppl;
        scanf("%d",&ppl);
        int men[ppl],women[ppl];
        for(i=0;i<ppl;i++)
            scanf("%d",&men[i]);
        for(i=0;i<ppl;i++)
            scanf("%d",&women[i]);
        sort(men,men+ppl);  //sorts array 'men' from zeroth to ppl-1 th index
        sort(women,women+ppl);
        long long ans=0;
        for(i=0;i<ppl;i++)
            ans+=men[i]*women[i]; //hotness maximised
        printf("%d\n",ans);
    }
    return 0;
}

SPOJ Problem Set (classical) 2148. Candy III Problem code: CANDY3

//http://www.spoj.com/problems/CANDY3/

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int ppl,i,sum=0,temp;
        scanf("%lld",&ppl);
        for(i=0;i<ppl;i++)
        {
            scanf("%lld",&temp);
            sum=(sum+temp)%ppl;
        }
        if(sum)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

SPOJ Problem Set (classical) 2123. Candy I Problem code: CANDY

// http://www.spoj.com/problems/CANDY/

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int a;
    int arr[10005];
    scanf("%d",&a);
    while(a!=-1)
    {
        int k,temp=0,temp1=0,i;
        for(i=0;i<a;i++)
        {
            scanf("%d",&arr[i]);
            temp+=arr[i];
        }
        sort(arr,arr+a);
        k=temp/a;
        if(temp%a!=0){
            printf("-1\n");
        }
        else
        {
            for(i=0;i<a;i++)
            {
                while(arr[i]>k)
                {
                    arr[i]--;
                    temp1++;
                }
            }
            printf("%d\n",temp1);
        }
        scanf("%d",&a);
    }
    return 0;
}

SPOJ Problem Set (classical) 4300. Rectangles Problem code: AE00

// http://www.spoj.com/problems/AE00/
#include<cstdio>
#include<cmath>

int main()
{
    int i,j,n,cnt=0;
    scanf("%d",&n);

    //    counting no. of rectangles
    for(i=1;i<=sqrt(n);i++)
        for(j=i+1;i*j<=n;j++)
            cnt++;

    //    counting no. of squares
    cnt+=sqrt(n);
    printf("%d",cnt);
    return 0;
}

SPOJ Problem Set (classical) 42. Adding Reversed Numbers Problem code: ADDREV

//http://www.spoj.com/submit/ADDREV/id=10772893
//mayur shingote

#include<stdio.h>
long int rev(long int n)
{
long int a[20]={0},i=0,m,sum=0;
while(n)
{
a[i++]=n%10;
n/=10;
}
m=1;
while(i--)
{
sum+=a[i]*m;
m*=10;
}
return sum;
}
int main()
{
long int  test,no1,no2,result;
scanf("%ld",&test);
while(test--)
{
scanf("%ld%ld",&no1,&no2);
result=rev(no1)+rev(no2);
printf("%ld\n",rev(result));
}
return 0;
}

SPOJ Problem Set (classical) 7974. What’s Next Problem code: ACPC10A

//http://www.spoj.com/problems/ACPC10A/
//mayur shingote :)
#include<stdio.h>
int main()
{
int a1,a2,a3;
while(1)
{
scanf("%d%d%d",&a1,&a2,&a3);
if(a1==0&&a2==0&&a3==0)
break;
if((a3-a2)==(a2-a1))
{
printf("AP %d\n",a3+(a3-a2));
}
else
{
printf("GP %d\n",a3*(a3/a2));
}
}
return 0;
}

SPOJ Problem Set (classical) 11. Factorial Problem code: FCTRL

//http://www.spoj.com/problems/FCTRL/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

int nInputs=Integer.parseInt(br.readLine());

for(int k=0;k<nInputs;k++)
{
int sum=0;
int num=Integer.parseInt(br.readLine());

while(num>4)
{
num=num/5;
sum=sum+num;
}
System.out.println(sum);

}

}

}

SPOJ Problem Set (classical) 24. Small factorials Problem code: FCTRL2

//http://www.spoj.com/problems/FCTRL2/
//Program to find factorial of small numbers
//mayur shingote :)
#include<stdio.h>
#include<string.h>
int main()
{
   int t,n,z,a[200],m,i,x,temp;
   scanf("%d",&t);
   while(t>0)
   {  scanf("%d",&n);
      a[0]=1;m=1;i=1;
      while(i<=n)
      {  temp=0;z=0;
         for(;z<m;z++)
         { x=a[z]*i+temp;
           a[z]=x%10;
           temp=x/10;
         }
         while(temp!=0)
         {  a[z++]=temp%10;
            temp/=10;
            m++;
         }
         i++;
      }
      for(i=--m;i>=0;i--)
      printf("%d",a[i]);
      t--;
      printf("\n");
   }
   return 0;
}