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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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