here is only basic implementation of problems for beginners. If you have any problem with any solution or any basic concept of programming or you want more efficient solution you can mail me.
my suggestion is not to copy and paste codes from here try to understand the logic and think why you were not able to solve it.

Tuesday 30 September 2014

Easiest loop 1

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

here after solving the equation
    p=(10*m+15+4*Sm)/(10*n+15+4*Sn)     
and for any m or n 
   p=3^(m-n)



#include<stdio.h>
int main(){
    long long t,m,n,p;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld",&n,&m);
        p=(m-n)%4;
        if(p==1)
            printf("3\n");
        else if(p==2)
            printf("9\n");
        else if(p==3)
            printf("7\n");
        else
            printf("1\n");
    }
    return 0;
}

potions class

  problem statement is here

#include<stdio.h>
int main(){
long long a,b,c,w,x,y,z,q,i,t,n,ar[100007],br[100006],l;
scanf("%lld",&t);
while(t--){
ar[0]=0;br[0]=0;
scanf("%lld %lld",&n,&q);
for(i=1;i<=n;i++){
scanf("%lld",&l);
ar[i]=ar[i-1]+l;
br[i]=br[i-1]+(l*i);
// printf("%lld %lld\n",ar[i],br[i]);
}
while(q--){
scanf("%lld %lld %lld %lld",&w,&x,&y,&z);
a=(w-x)*(ar[x+z]-ar[x+y-1]);
b=br[x+z]-br[x+y-1];
c=a+b;
c%=1000000007;
printf("%lld\n",c);
}
}
return 0;
}

Sunday 28 September 2014

Dijkstra’s algorithm using adjacency matrix

this program finds distance of all vertexes from a given source vertex
time complexity using adjacency matrix is O(v^2)
it doesn't work for negative weighted graphs


#include <stdio.h>
#include <limits.h>
int n;
int takemin(int dist[],int visited[]){
   int min=INT_MAX,min_index,i;
  for(i=0;i<n;i++)
     if(visited[i]==0 && dist[i] <= min){
      min=dist[i];
min_index=i;
     }
  return min_index;
}

int printfinal(int dist[],int n){
int i;
   printf("Vertex   Distance from Source\n");
   for(i=0;i<n;i++)
      printf("%d                 %d\n",i,dist[i]);
}

void dijkstra(int graph[n][n], int source){
     int dist[n],visited[n],i,j,u;
     for(i=0;i<n;i++){
      dist[i]=INT_MAX;
visited[i]=0;
     }
     //taking distance of source as 0
    dist[source]=0;
    for(j=0;j<n-1;j++){
       //take min distance vertex which is not taken yet
       u=takemin(dist,visited);
  //mark the picked vertex as visited
       visited[u]=1;
//update the distances of vertexes adjacent to the picked vertex
       for(i=0;i<n;i++){
        if(graph[u][i]>0 && visited[i]==0){
        if(dist[u]+graph[u][i]<dist[i] || dist[i]==INT_MAX){
        dist[i]=dist[u]+graph[u][i];
        }
        }
    }
    }
    printfinal(dist,n);
}

int main(){
int i,j;
printf("Enter no of vertexes\n");
scanf("%d",&n);
int graph[n][n];
printf("Enter adjacency matrix\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&graph[i][j]);
}
}
  dijkstra(graph, 0);
  return 0;
}

Saturday 27 September 2014

Hackerrank candies

// https://www.hackerrank.com/challenges/candies

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

int main() {

    long a=0,n,i,j,ar[100003],dp[100003];
    scanf("%ld",&n);
    scanf("%ld",&ar[0]);
    dp[0]=1;
    for(i=1;i<n;i++){
        scanf("%ld",&ar[i]);
        if(ar[i]>ar[i-1]){
            dp[i]=dp[i-1]+1;
        }else{
            dp[i]=1;
        }
    }
    for(i=n-2;i>=0;i--){
        if(ar[i]>ar[i+1] && dp[i]<=dp[i+1]){
            dp[i]=dp[i+1]+1;
        }
    }
    for(i=0;i<n;i++){
        //printf("%ld  ",dp[i]);
        a+=dp[i];
    }
    printf("%ld\n",a);
    return 0;
}

red john is back

// https://www.hackerrank.com/challenges/red-john-is-back

problem statement is here


#include<stdio.h>
int ar[300000]={0};
long long fact(long long a){
long long i,b=1;
for(i=2;i<=a;i++){
b*=i;
}
return b;
}
int main(){
    long long x,a,b,c,d,e,i,j,z;
    ar[0]=ar[1]=1;
    for(i=2;i<3000;i++){
    if(ar[i]==0){
    for(j=i*2;j<300000;j+=i){
    ar[j]=1;
    }
    }
    }
scanf("%lld",&d);
    while(d--){
        scanf("%lld",&a);
        if(a<4){
            b=1;
        }else{
            e=a/4;
            b=1;
            for(i=1;i<=e;i++){
            z=1;
            for(x=a-i*4+1;x<=a-i*4+i;x++){
            z*=x;
            }
            z/=fact(i);
            // printf("z=%lld\n",z);
            b+=z;
            }
        }
        c=0;
        for(i=2;i<=b;i++){
            if(ar[i]==0){
                c++;
            }
        }
        printf("%lld\n",c);
    }
 
    return 0;
}

tip top game

 problem statement is here


#include<stdio.h>
#include<math.h>
int main(){
    long long int a,b,c=1;
    long int t;
    scanf("%ld",&t);
    while(t--){
               scanf("%lld",&a);
               b=sqrt(a);
               if(b*b==a){
                printf("Case %lld: Yes\n",c);
               }else{
                printf("Case %lld: No\n",c);
               }
               c++;
    }
        return 0;
     }

Friday 26 September 2014

Spoj prime time

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

#include<stdio.h>
int sieve[100010]={0};
long prime_table() {
    int i, j;
    for (i = 2; i <=50000; i+= 2)
           sieve[i]=1;

        for (i = 3; i <=50000; i += 2){
                if (sieve[i]==0){
                    for (j=i; (j*i) <=50000; j += 2){
                        sieve[j*i] = 1;
                    }
                }
        }
}
int main(){
prime_table();
long long a,t,n,i,j,u,x,v,p,s;
scanf("%lld",&n);
a=n;x=0;p=2;
while(a){
a=n;
x+=(n/p);
p*=2;
a/=p;
}
printf("%lld^%lld",2,x);
for(i=3;i<=n;i+=2){
if(sieve[i]==0){
a=n;x=0;p=i;
while(a){
a=n;
x+=(n/p);
p*=i;
a/=p;
}
printf(" * %lld^%lld",i,x);
}
}
printf("\n");
return 0;
}

Thursday 25 September 2014

Spoj alia and 3 khans

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

#include<stdio.h>
int main(){
long long t,a,b,n,c,i,j,k,x,u,p=0,s=0,q,l;
int ar[100],br[100];
scanf("%lld",&t);
q=t;
while(t--){
scanf("%lld",&n);
a=n;i=0,j=0,k=0;
while(a>0){
ar[i]=a%2;
a/=2;
br[i]=ar[i];
i++;
}
// printf("%lld\n",i);
x=0;
for(j=0;j<i;j++){
if(ar[j]==0){
if(ar[j+1]==1){
u=ar[j];
ar[j]=ar[j+1];
ar[j+1]=u;
break;
}
}
if(ar[j]==1){
x++;
}
}
//printf("%lld\n",j);
if(j==i){
b=-1;
}else{
for(k=j-1;k>=0;k--){
if(x>0){
ar[k]=1;
x--;
}else{
ar[k]=0;
}
}
b=0;l=1;
for(j=0;j<i;j++){

b+=(ar[j]*l);
l*=2;
// printf("%d  ",mult(2,j));
}
}
ar[i]=0;
br[i]=0;
i++;
x=0;j=0;k=0;
for(j=0;j<i;j++){

if(br[j]==1){
if(br[j+1]==0){
u=br[j];
br[j]=br[j+1];
br[j+1]=u;
break;
}
}
if(br[j]==1){
x++;
}
}
// printf("%lld\n",x);
for(k=0;k<=j-1;k++){
if(x>0){
br[k]=1;
x--;
}else{
br[k]=0;
}
// printf("%d  ",br[k]);
}
c=0;l=1;
for(j=0;j<i;j++){
c+=(br[j]*l);
l*=2;
}
if(n==0){
c=-1;
}
//printf(" %lld %lld %lld\n",n,b,c);
if(n*n==b*c){
p++;
}
s+=(c-b);
//printf("%lld %lld\n",p,s);
}
double y,z;
y=(double)p/(double)q;
z=(double)s/(double)q;
printf("%.6lf %.6lf\n",y,z);
return 0;
}

Wednesday 24 September 2014

Spoj alia and handsome devil

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

#include<stdio.h>
#include<math.h>
int main(){
long long a,b,c=1,i,j,t,n,ar[1000],m;
ar[0]=0;ar[1]=1;ar[2]=1;
for(i=3;i<100;i++){
ar[i]=ar[i-1]+ar[i-2];
}
// printf("%lld\n",ar[94]);
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&m);
long long sum=0,sum1=0;
b=0;
a=sqrt(n);
if(a*a==n){
sum+=a;
a--;

}
for(i=2;i<=a;i++){
if(n%i==0){
sum+=i;
sum+=(n/i);
//printf("%lld\n",sum);
}
}
sum+=1;
sum%=m;
a=sqrt(sum);
if(a*a==sum){
sum1+=1;
a--;
}
for(i=2;i<=a;i++){
if(sum%i==0){
sum1+=2;
}
}
sum1+=1;
// printf("%lld\n",sum1);
for(i=0;i<96;i++){
if(ar[i]==sum1){
b=1;
break;
}
}
if(b==1){
printf("Case #%lld : YES.\n",c);
}else{
printf("Case #%lld : NO.\n",c);
}
c++;
}

return 0;
}

Spoj a famous icpc team

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

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
   long long int a[4],p;
   int j,i=1;
   while(scanf("%lld ",&a[0])!=EOF)
    {
     
        for(j=1;j<4;j++)
        {  
            scanf("%lld",&a[j]);
           
        }
        sort(a,a+4);
        p=a[3]+a[2];
        printf("Case %d: %lld\n",i,p);
        i++;
    }
    return 0;
}



Spoj Espionage

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

#include<stdio.h>
int main(){
long long int a,n,t,i,j,c=1,r,b;
scanf("%lld",&t);
while(t--){
long int ar[2000]={0},br[2000]={0},u=0;
scanf("%lld %lld",&n,&r);
while(r--){
scanf("%lld %lld",&a,&b);
ar[a]++;
br[b]++;
}
for(i=0;i<n;i++){
if(ar[i]>0 && br[i]>0){
u=1;
break;
}
}
if(u==1){
printf("Scenario #%lld: spied\n",c);
c++;
}else{
printf("Scenario #%lld: spying\n",c);
c++;
}
}
return 0;
}

Monday 22 September 2014

Spoj princes farida

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

#include <stdio.h>
unsigned long long int dp[1010];
int t,n;
unsigned long long int max(unsigned long long int a, unsigned long long int b){
return a > b ? a : b;
}
int main(){
int i, h;
scanf("%d", &t);
for(h=1;h<=t;h++){
scanf("%d",&n);
for(i=0;i<n;i++){
int k;
scanf("%d",&k);
dp[i]=max(k+(i>1?dp[i-2]:0),i>0?dp[i-1]:0);
}
printf("Case %d: %llu\n", h, dp[n-1]);
}

return 0;
}

Saturday 20 September 2014

Spoj is it a tree

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

#include<stdio.h>
struct set{
int parent;
int rank;
};
int find(struct set ar[],int a){
if(ar[a].parent==-1){
return a;
}
find(ar,ar[a].parent);
}
int main(){
int a,b,c,d,e,x,i=0;
scanf("%d %d",&a,&b);
struct set ar[a+1];
for(x=0;x<=a;x++){
ar[x].parent=-1;
ar[x].rank=0;
}
while(b--){
scanf("%d %d",&c,&d);
int g=find(ar,c);
int f=find(ar,d);
if(g==f){
i=1;
}else{
if(ar[g].rank<ar[f].rank)
        ar[g].parent=f;
    else if(ar[g].rank>ar[f].rank)
        ar[f].parent=g;
    else{
        ar[f].parent=g;
        ar[g].rank++;
    }
}
}
if(i==0){
printf("YES\n");
}else{
printf("NO\n");
}
return 0;
}

dfs traversal of a graph using adjacency list

#include<stdio.h>
#include<vector>
using namespace std;
void dfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  visited[i]=1;
  printf("%d\n",i);
  for(j=0;j<ar[i].size();j++){
  if(visited[ar[i][j]]==0){
  dfs(ar,visited,ar[i][j],n);
  }
  }
}
int main(){
  int a,b,i,j,n,m;
  printf("no of nodes\n");
  scanf("%d",&n);
  vector<int> ar[n+9];
  int visited[n+9];
  for(i=0;i<n+9;i++){
  visited[i]=0;
  }
  printf("no of edges\n");
  scanf("%d",&m);
  for(j=0;j<m;j++){
    scanf("%d %d",&a,&b);
    ar[a].push_back(b);
    ar[b].push_back(a);
  }
  for(i=1;i<=n;i++){
  if(visited[i]==0){
    dfs(ar,visited,i,n);
  }
  }
  return 0;
}

Friday 19 September 2014

Spoj gopi and sandwich

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

#include<stdio.h>
long long arr[1000006];
void solution(){
long i;
arr[2]=2;
for(i=3;i<=1000000;i++){
arr[i]=(arr[i-1]*(arr[i-1]+1))%1000000007;
}
}
int main(){
solution();
long long t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
printf("%lld\n",arr[n]%1000000007);
}
return 0;
}

Thursday 18 September 2014

Spoj database

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

#include <cstdio>
#include <algorithm>
using namespace std;

pair< long int, long int > ar[100000];

inline bool comp(const pair< int, int > &a, const pair< int, int > &b) {
return (a.first == b.first) ? a.second < b.second : a.first < b.first;
}

int main() {
long int t, i, n, l,r,c=1,u;
scanf("%ld", &t);
while(t--) {
u=0;
scanf("%ld %ld", &r,&n);
for(i = 0; i < n; i++)
scanf("%ld %ld", &ar[i].first, &ar[i].second);
sort(ar, ar + n, comp);
for(i=0;i<n;i++){
if(ar[i].first==ar[i+1].first){
if(ar[i].second==ar[i+1].second){
u=1;
break;
}
}
}
if(u==1){
printf("Scenario #%ld: impossible\n",c);
}else{
printf("Scenario #%ld: possible\n",c);
}
c++;
}
return 0;
}

Spoj candies and milestones

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

#include<stdio.h>

//fast input
inline int fastRead_int() {
    register int c = getchar_unlocked();
    int x = 0;
    int neg = 0;
    for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
    if(c=='-') {
    neg = 1;
    c = getchar_unlocked();
    }
    for(; c>47 && c<58 ; c = getchar_unlocked()) {
    x = (x<<1) + (x<<3) + c - 48;
    }
    if(neg)
    x = -x;
   
    return x;
}


int main(){
long long int t,n,m,ar[100000],i,j,p,q;
t=fastRead_int();
while(t--){
p=0;q=0;
long long min=0,minb=0;
n=fastRead_int();
m=fastRead_int();
ar[0]=fastRead_int();
for(i=1;i<m;i++){
ar[i]=fastRead_int();
if(ar[i]>ar[i-1]){
p-=(ar[i]-ar[i-1]);
q+=(ar[i]-ar[i-1]);
if(p<minb){
minb=p;
}
}else if(ar[i]<ar[i-1]){
p+=(ar[i-1]-ar[i]);
q-=(ar[i-1]-ar[i]);
if(q<min){
min=q;
}
}else{
q--;
if(q<min){
min=q;
}
}
}
j=(-1)*minb+(-1)*min+1;
if(j>n){
printf("-1\n");
}else{
printf("%lld\n",(-1)*min+1);
}
}
return 0;
}

Wednesday 17 September 2014

Spoj Candy 1

#include<stdio.h>
int main(){
    long long int sum,sumr;
    int p,ar[10000],l,i,x;
    while(1){
            sum=0;
            sumr=0;
            scanf("%d",&p);
            if(p==-1)
            break;
            for(i=0;i<p;i++){
                scanf("%d",&ar[i]);
                sum=sum+ar[i];
            }
            l=sum%p;
            if(l==0){
x=sum/p;
                for(i=0;i<p;i++){
                    if(ar[i]>x)
                    sumr=sumr+(ar[i]-x);
            }
                printf("%lld\n",sumr);
        }
            else
                printf("-1\n");
    }
    return 0;
}

Spoj candy distribution

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
   long long  a,i,sum,ar[100000],pr[100000];
   while(1){
        sum=0;
    scanf("%lld",&a);
    if(a==0)
    break;
    for(i=0;i<a;i++){
            scanf("%lld",&ar[i]);
        }
        sort(ar,ar+a);
        for(i=0;i<a;i++){
            scanf("%lld",&pr[i]);
        }
    sort(pr,pr+a);
        for(i=0;i<a;i++){
            sum=sum+ar[i]*pr[a-i-1];
        }
        printf("%lld\n",sum);
    }
    return 0;
}
                                   
                   






Tuesday 16 September 2014

Spoj aliens at the train again

#include<stdio.h>
long long min(long long x,long long y){
if(x<y)
return x;
return y;
}
int main(){
long long n,k,ar[100009],br[100009],i,j,sum1[100000],sum2[100000],u;
scanf("%lld %lld",&n,&k);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<n;i++){
scanf("%lld",&br[i]);
}
sum1[0]=ar[0];sum2[0]=br[0];
if(sum1[0]>k && sum2[0]>0){
printf("0 0\n");
}else{
for(i=1;i<n;i++){
sum1[i]=min(sum1[i-1]+ar[i],sum2[i-1]+ar[i-1]+ar[i]);
sum2[i]=min(sum2[i-1]+br[i],sum1[i-1]+br[i-1]+br[i]);
if(sum1[i]>k && sum2[i]>k)
break;
}
for(j=i-1;j>=0;j--){
u=min(sum1[j],sum2[j]);
if(u<=k){
printf("%lld %lld\n",j+1,u);
break;
}
}
}
return 0;
}

Spoj aliens at the train

#include<stdio.h>
int main(){
    long long t,a,b,c,i,j;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld",&a,&b);
        long long ar[a];
        for(i=0;i<a;i++)
        scanf("%lld",&ar[i]);
        long long p=0,x=0,h=0,min=1000000,mi=0;
        for(i=0;i<a;i++){
            if(b>=x+ar[i]){
                x+=ar[i];
                h++;
            }else{
                x+=ar[i];
                h++;
                while(x>b){
                    x-=ar[p];
                    h--;
                    p++;
                }
            }
            if(mi<h){
                mi=h;
                min=x;
        }else if(mi==h){
                if(min>x){
                    min=x;
            }
        }
        }
        printf("%lld %lld\n",min,mi);
    }
    return 0;
}

Spoj genie sequence

#include<stdio.h>
int main(){
int a,b,n,u,t,i,z;
scanf("%d",&t);
while(t--){
u=0;
int ar[1000]={0};
scanf("%d",&n);
b=n;
while(b--){
scanf("%d",&a);
if(a>=n){
u=1;
}else{
ar[a]++;
}
}
for(i=0;i<n/2;i++){
z=ar[i]+ar[n-1-i];
if(z!=2){
u=1;
break;
}
}
if(n%2!=0){
if(ar[n/2]!=1){
u=1;
}
}
if(u==1){
printf("NO\n");
}else{
printf("YES\n");
}
}
return 0;
}

Monday 15 September 2014

Spoj the last digit re-visited

#include<stdio.h>
#include<string.h>
int main(){
    long long int n;
    int test,l,t,j,m,x;
    char a[1000];
    scanf("%d",&test);
    for(j=0;j<test;j++){
        scanf("%s %lld",a,&n);
    m=a[strlen(a)-1]-48;
    if(m==0&&n==0)
        t=0;
    else if(n==0)
          t=1;
    else{        
l=n%4;
            if(l==0)
            x=pow(m,4);
            else
                x=pow(m,l);
            t=x%10;
}
    printf("%d\n",t);
    }
    return 0;
}

                     



Spoj the last digit

#include<stdio.h>
#include<math.h>
int main(){
    long long int a,m,n,l,i,x,t;
    scanf("%lld",&a);
    for(i=0;i<a;i++){
        scanf("%lld %lld",&m,&n);
        if(m==0&&n==0)
        t=0;
        else if(n==0)
            t=1;
        else{
l=n%4;
            if(l==0)
                x=pow(m,4);
            else
                x=pow(m,l);
            t=x%10;
}
        printf("%lld\n",t);
    }
    return 0;
}

Spoj dota heroes

#include<stdio.h>
int main(){
    int a,i,j,k,h[100000],d,t,n,l;
    scanf("%d",&a);
    for(i=0;i<a;i++){
        scanf("%d %d %d",&n,&t,&d);
        for(j=0;j<n;j++){
            scanf("%d",&h[j]);
        }
        l=0;
        for(k=0;k<t;k++){
            for(j=0;j<n;j++){
            if(h[j]>d){
                    h[j]=h[j]-d;
                    l=l+1;
                    break;
            }
            }
        }
        if(l==t)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Spoj white hats

#include<stdio.h>
int main(){
int a,b,c,ar[1000]={0},n,i,j,max=-1,min=10000;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a);
if(a>max){
max=a;
}
if(a<min){
min=a;
}
ar[a]++;
}
// printf("%d %d\n",max,min);
if(max-min>=2){
j=-1;
// printf("1\n");
}else if(max==n-1 && ar[max]==n){
j=max+1;
// printf("2\n");
}else if(max==min && min==0){
j=0;
// printf("3\n");
}else if(ar[max]==n-max && ar[min]==max){
j=max;
// printf("4\n");
}else{
j=-1;
// printf("5\n");
}
printf("%d\n",j);
return 0;
}

Spoj majority

#include<stdio.h>
int main(){
    long int t,n,p,s,i,j,max;
    scanf("%ld",&t);
    while(t--){
        max=0;
        scanf("%ld",&n);
        int ar[n],br[10000]={0};
        for(i=0;i<n;i++){
            scanf("%d",&ar[i]);
        br[ar[i]+1000]+=1;
            if(max<br[ar[i]+1000]){
                max=br[ar[i]+1000];
                p=ar[i];
            }
        }
        if(max>n/2)
        printf("YES %ld\n",p);
        else
            printf("NO\n");
    }
    return 0;
}

Sunday 14 September 2014

Spoj gopu and validity arrangement

#include<stdio.h>
int main(){
long long t,a,ar[200000],i,n,v;
scanf("%lld",&t);
while(t--){
v=0;
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
if(ar[i]>i){
v=1;
}
}
if(v==1){
printf("NO\n");
}else{
printf("YES\n");
}
}
return 0;
}

Spoj enough of analyzing lets play

#include<stdio.h>
int main(){
int t,a,n,i,j,b,u,ar[10000],c=1;
scanf("%d",&t);
while(t--){
j=0;
scanf("%d",&n);
scanf("%d",&ar[0]);
if(n>=2){
scanf("%d",&ar[1]);
u=ar[0]^ar[1];
}
for(i=2;i<n;i++){
scanf("%d",&ar[i]);
u^=ar[i];
}
if(n==1){
printf("Case %d: 1\n",c);
}else{
for(i=0;i<n;i++){
a=u^ar[i];
if(a<ar[i]){
j++;
}
}
printf("Case %d: %d\n",c,j);
}
c++;
}
return 0;
}

Saturday 13 September 2014

Spoj love story

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
long long a,b,i,j,n,ar[10000],u,p,t,k;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
scanf("%lld",&a);
sort(ar,ar+n);
for(i=0;i<n-2;i++){
j=i+1;k=n-1;u=0;
while(j<k){
if(ar[i]+ar[j]+ar[k]==a){
u=1;
break;
}else if(ar[i]+ar[j]+ar[k]>a){
k--;
}else{
j++;
}
}
if(u==1){
break;
}
}
if(u==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}

dfs traversal of a graph using adjacency matrix

// complexity O(V+E)

#include<stdio.h>
int ar[100][100];
void dfs(int visited[],int i,int n){
int j;
visited[i]=1;
printf("%d\n",i);
for(j=0;j<n;j++){
if(ar[i][j]==1 && visited[j]!=1){
dfs(visited,j,n);
}
}
}
int main(){
int a,b,i,j,n,visited[101];
printf("Enter no of vertices\n");
scanf("%d",&n);
printf("Enter adjacency matrix\n");
for(i=0;i<n;i++){
visited[i]=0;
for(j=0;j<n;j++){
scanf("%d",&ar[i][j]);
}
}
for(i=0;i<n;i++){
if(visited[i]==0){
dfs(visited,i,n);
}
}
return 0;
}

Spoj encode message

#include<stdio.h>
#include<string.h>
int main(){
int i,j,t,u,p,m,a,b,c;
char ar[10],br[1000],cr[1000];
scanf("%d",&t);
while(t--){
scanf("%s",ar);
scanf("%s",br);
a=strlen(ar);
c=2*a;
b=strlen(br);
for(i=0;i<b;i++){
p=i%c;
if(p<a){
u=br[i]-(ar[p]-48);
}else{
p=c-1-p;
u=br[i]-(ar[p]-48);
}
if(u<97){
u=u+123-97;
}
printf("%c",u);
}
printf("\n");
}
return 0;
}

Friday 12 September 2014

Spoj world and contients

#include<stdio.h>
int parent[100002];
int find(int i){
    if(parent[i]!=i)
        parent[i]=find(parent[i]);
    return parent[i];
}
int main(){
int a,b,c,x,i,m,n;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
parent[i]=i;
}
x=n;
while(m--){
scanf("%d %d",&b,&c);
int b_root=find(b);
    int c_root=find(c);
    if(b_root!=c_root){
            parent[b_root]=c_root;
            x--;
    }
}
printf("%d\n",x-1);
return 0;
}

Spoj just next !!!

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    long long int t,i,j,p,x,h,n,k;
    scanf("%lld",&t);
    while(t--){        
              p=0;
              int a[1000000],count[10]={0};
              scanf("%lld",&n);
              for(i=0;i<n;i++){
                       scanf("%d ",&a[i]);
               }
               for(i=n-1;i>=0;i--){
                        count[a[i]]++;
                        for(j = a[i]+1; j < 10; j++){
                                if(count[j]>0){
                                p=1;
                                break;
                                }
                        }
                        if(p==1){
                                a[i] = j; count[j]--;
                                k=i+1;
                            for(j = 0;j < 10; j++){
                                        while(count[j]--)
                                        a[k++] = j;
                                }
                                break;
                        }
               }
            if(i >= 0) {
                        for(i = 0; i < n; i++)
            printf("%d", a[i]);
                        printf("\n");
                }else{
                printf("-1\n");
                }
        }
        return 0;
    }

Spoj the ball game

#include<stdio.h>
int main(){
double t,n,z,u;
scanf("%lf",&t);
while(t--){
scanf("%lf",&n);
z=n/(n+1);
printf("%.8lf\n",z);
}
return 0;
}

Spoj touch the venom

#include<stdio.h>
int main(){
long int a,b,c,i,j,k,p,u,t,x,y,z;
scanf("%ld",&t);
while(t--){
scanf("%ld %ld %ld",&a,&b,&c);
u=1;
a-=b;y=0;
for(i=1; ;i++){
if(a<=0){
break;
}
x=((10000*i)*((2*(2*b-c))+(((i*10000)-1)*b))/2);
if(x>=a){
break;
}else{
y=x;
u+=20000;
}
}
z=(i-1)*10000;
for(i=1; ;i++){
if(a<=0){
break;
}
k=z+(1000*i);
x=(k*((2*(2*b-c))+((k-1)*b))/2);
if(x>=a){
break;
}else{
y=x;
u+=2000;
}
}
z=k-1000;
for(i=1; ;i++){
if(a<=0){
break;
}
k=(z+(100*i));
x=(k*((2*(2*b-c))+((k-1)*b)))/2;
if(x>=a){
break;
}else{
y=x;
u+=200;
}
}
z=k-100;
for(i=1; ;i++){
if(a<=0){
break;
}
k=(z+(10*i));
x=(k*((2*(2*b-c))+((k-1)*b))/2);
if(x>=a){
break;
}else{
y=x;
u+=20;
}
}
a-=y;
z=k-10;
k=((2*b-c)+((z)*b));
for(j=0; ;i++){
if(a<=0){
break;
}
a-=k;
k+=b;
u+=2;
}
printf("%ld\n",u);
}
return 0;
}

Working in beijing

#include<stdio.h>
int main(){
unsigned long long int t,n,a,b,i,c=1,j,sum,ar,x;
scanf("%llu",&t);
while(t--){
scanf("%llu %llu %llu",&n,&a,&b);
sum=(n*b+2*a);
scanf("%llu",&ar);
x=ar;
for(i=1;i<n;i++){
scanf("%llu",&ar);
j=(ar-x-1)*b;
if(j<=2*a)
sum+=j;
else
sum+=(2*a);
x=ar;
}
printf("Case #%llu: %llu\n",c,sum);
c++;
}
return 0;
}

Wachovia Bank

#include<stdio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int n){
   int i, w;
   int k[n+1][W+1];
   for (i = 0; i <= n; i++){
       for (w = 0; w <= W; w++){
           if (i==0 || w==0)
               k[i][w] = 0;
           else if (wt[i-1] <= w)
                 k[i][w] = max(val[i-1] + k[i-1][w-wt[i-1]],  k[i-1][w]);
           else
                 k[i][w] = k[i-1][w];
       }
   }

   return k[n][W];
}

int main(){
    int a,t,b,ar[10000],i,j,n,k,w,br[10000];
    scanf("%d",&t);
    while(t--){
    scanf("%d %d",&w,&n);
    for(i=0;i<n;i++){
    scanf("%d %d",&ar[i],&br[i]);
    }
    printf("Hey stupid robber, you can get %d.\n", knapSack(w, ar, br, n));
    }
    return 0;
}

He is offside

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int m,n,i,j;
    while(1){
        scanf("%d %d",&m,&n);
        if(m==0 && n==0)
           break;
        int ar[m],br[n];
        for(i=0;i<m;i++)
            scanf("%d",&ar[i]);
        for(i=0;i<n;i++)
            scanf("%d",&br[i]);
        sort(ar,ar+m);
        sort(br,br+n);
        if(ar[0]<br[1]){
            printf("Y\n");
        }else{
            printf("N\n");
    }
    }
    return 0;
}

Seinfeld

#include<stdio.h>
#include<string.h>
int main(){
int a,b,c=1,d,i,j;
char ar[100000];
while(1){
int y=0,z=0;
d=0;
scanf("%s",ar);
if(ar[0]=='-'){
break;
}
a=strlen(ar);
for(i=0;i<a;i++){
if(ar[i]=='{'){
y++;
}else if(ar[i]=='}'){
z++;
}
if(z<=y){
y-=z;
z=0;
}else{
d+=1;
y++;
z--;
}
}
if(y>z){
y-=z;
d+=y/2;
}else if(z>y){
z-=y;
d+=z/2;
}
printf("%d. %d\n",c,d);
c++;
}
return 0;
}