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