Amusing numbers

problem statement is here

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

int main()
{
    long long int a,t,i,j,n,b;
    scanf("%lld",&t);
    while(t--){
               scanf("%lld",&a);
               for(i=1; ;i++){
                        if(a>(pow(2,i)-2) && a<=(pow(2,i+1)-2)){
                                          b=a-(pow(2,i)-2);
                                           break;
                                           }
                        }
                        n=i;
               for(j=1;j<=n;j++){
                                 if(b>pow(2,i-1)){
                                                  printf("6");
                                                  b=b-pow(2,i-1);
                                                  }else{
                                                        printf("5");
                                                        }
                                 i--;
                                 }
               printf("\n");
               }
    return 0;
}

Playing with isosceles triangle

problem statement is here

#include<stdio.h>
#include<math.h>
 int main() {
long int n,t,s,flag,i,c;
scanf("%ld", &t);
while(t--) {
scanf("%ld",&s);
flag=0;
if(s%2==0){
while(s%2==0)
s=s/2;
}
n=(sqrt(s));
for(i=3;i<=n;i+=2){
if(s%i==0){
if(i%4==1)
flag = 1;
while(s%i==0)
s=s/i;
}
if(s==1)
break;
}
if(s!=1&&s%4==1)
flag=1;
if(flag==0){
printf("NO\n");
} else {
printf("YES\n");
}
}
return 0;
}

Counting Triangles

problem statement is here

#include<stdio.h>
int main(){
        long long int totel,x,y;
        scanf("%lld",&x);
        while(x--){
                scanf("%lld",&y);
                totel=(y*(y+2)*(2*y+1))/8;
                printf("%lld\n",totel);
        }
        return 0;
}

Traversing Grid

problem statement is here

#include<stdio.h>
int main(){
    long long int n,m;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld",&n,&m);
        if(n%2==0 && m%2==0){
            if(n>m){
            printf("U\n");
            }else if(m>=n)
                    printf("L\n");
        }
        else if(n%2!=0 && m%2!=0){
            if(n>m)
                printf("D\n");
            else if(m>=n)
                printf("R\n");
        }
        else{
            if(n%2==0 && m%2!=0)
                {
                    if(n>m)
                        printf("D\n");
                    else
                        printf("L\n");
                }
            if(n%2!=0 && m%2==0)
                {
                    if(n<m)
                        printf("R\n");
                    else
                        printf("U\n");
                }
        }
    }
    return 0;
}

To and Fro

problem statement is here

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

int main()
{
    int a,i,j,n,b,k;
    char ar[210];
    while(1){  
                 scanf("%d",&a);
                 if(a==0)
                 break;
                 else{
                      scanf("%s",ar);
                      b=strlen(ar);
                      j=a;
                      for(i=0;i<a;i++){
                                       printf("%c",ar[i]);
                                       for(k=2; ;k+=2){
                                                if((k*j-i-1)<b){
                                                                printf("%c",ar[k*j-i-1]);
                                                                }else{
                                                                      break;
                                                                      }
                                                if((k*j+i)<b){
                                                              printf("%c",ar[k*j+i]);
                                                              }else{
                                                                    break;
                                                                    }
                                                }
                                       }
                      printf("\n");
                      }
                 }
    return 0;
}
   

Movie Theatre Madness

problem statement is here

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct compare
{
  bool operator()(const long long & l, const long long & r)
  {
      return l > r;
  }
};

int main(){
priority_queue<long long,vector<long long>, compare > pq;
int n,i,a;
long long ar[100005],max=1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<n;i++){
pq.push(ar[i]);
while(1){
if(pq.top()==ar[i]){
break;
}else{
max=(max*(ar[i]))%1000000007;
pq.pop();
}
}
}
max=max%1000000007;
printf("%lld\n",max);

return 0;
}

Finding the Tesserect

problem statement is here

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main(){

    int t;

    scanf("%d\n",&t);

    while(t--)

    {

        int n,i;

        scanf("%d\n",&n);

        long long int a,b;

        scanf("%lld",&a);

        char ar[1000000],br[1000000];

        for(i=1;i<n;i++){

            scanf("%lld",&b);

            if(b>a){

                ar[i-1]='G';

            }else if(b==a){

                ar[i-1]='E';

            }else{

                ar[i-1]='L';

            }

            a=b;

        }

        ar[n]='\0';

        scanf("%s",br);

        if(strstr(ar,br))

            printf("YES\n");

        else

        printf("NO\n");

    }

    return 0;

}

A Famous ICPC Team

problem statement is here

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

Balanced base-3

problem statement is here

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

War

problem statement is here

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
long long int s,ar[100009],br[100009],i,j,z,p,a;
scanf("%lld",&s);
for(i=0;i<s;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<s;i++){
scanf("%lld",&br[i]);
}
sort(ar,ar+s);
sort(br,br+s);
z=s-1;p=0;
for(i=s-1;i>=0;i--){
if(ar[i]<br[z]){
p++;
z--;
}
}
printf("%lld\n",p);
return 0;
}

Faridi and Yadav

problem statement is here

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

int main(){
double x,y,r,t;
scanf("%lf",&t);
while(t--){
scanf("%lf%lf",&x,&y);
r=2*(sqrt((x*x)-(y*y)));
printf("%.3lf\n",r );
}
return 0;
}

Party

problem statement is here

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

int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
printf("%d\n", max(0, n-2));
}
return 0;
}

Count on Cantor

problem statement is here

#include<stdio.h>

int main()
{
    long long int t,a,b,c,i,j,k;
    scanf("%lld",&t);
    while(t--){
               scanf("%lld",&a);
               for(i=0; ;i++){
                        if(((i*(i+1))/2)<a && a<=(((i+1)*(i+2))/2) ){
                                           b=a-((i*(i+1))/2);
                                           break;
                                           }
                        }
                        c=i+1;
                        if(c%2==0){
                                   j=b;
                                   k=c+1-b;
                                   }else{
                                         j=c+1-b;
                                         k=b;
                                         }
                        printf("TERM %lld IS %lld/%lld\n",a,j,k);
               }
    return 0;
}

Black Widow Rings

problem statement is here

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

Pattern Find

problem statement is here

it is a basic concept of KMP algorithm

if u want to read about KMP algorithm u can find it here

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

int zr[1000002],q;

void computeLPSArray(char *pat, int M, int *lps){

    int len=0,i=1;

    lps[0]=0;

    while (i < M){

       if (pat[i] == pat[len]){

         len++;

         lps[i] = len;

         i++;

       }else{

         if (len != 0){

           len = lps[len-1];

         }else{

           lps[i] = 0;

           i++;

         }

       }

    }

}

void KMPSearch(char *pat, char *txt){

    int M = strlen(pat);

    int N = strlen(txt);

    int *lps = (int *)malloc(sizeof(int)*M);

    int j=0,i=0; 

    computeLPSArray(pat, M, lps);

    while (i < N){

      if(pat[j] == txt[i]){

        j++;

        i++;

      }

   if (j == M){

        zr[q++]=i-j+1;

        j = lps[j-1];

      }else if (i < N && pat[j] != txt[i]){

        if (j != 0)

         j = lps[j-1];

        else

         i = i+1;

      }

    }

    free(lps);

}

int main(){

   int t,i;

   scanf("%d",&t);

   while(t--){

    q=0;

    char ar[1000006],br[1000005];

    scanf("%s %s",ar,br);

    KMPSearch(br,ar);

    if(q==0){

    printf("Not Found\n");

    }else{

    printf("%d\n",q);

    for(i=0;i<q;i++){

    printf("%d ",zr[i]);

    }

    printf("\n");

    }

   }

   return 0;

}

Playing with GCD

problem statement is here

#include<stdio.h>

long long ar[100004];

void etf(){

     long long k,i,z;

     ar[0]=0;

     for(k=1;k<100001;k++){

      long long n=k;

      long long r=n;

        for(i=2;i*i<=n;i++){ 

          if (n%i==0) 

          r-=r/i; 

          while(n%i==0) 

          n/=i; 

       } 

       if (n>1)

        r-=r / n; 

       z=k-r;

       ar[k]=ar[k-1]+z;

   } 

}

int main(){

    long long t,num,c=1;

    etf();

    scanf("%lld",&t);

    while(t--){

        scanf("%lld",&num);

        printf("Case %lld: %lld\n",c,ar[num]);

        c++;

    }

    return 0;

}

Game of chocolate

problem statement is here

#include<stdio.h>

long long gcd(long long a,long long b){

    if(b==0){

        return a;

    }

return gcd(b,a%b);

}

int main(){

long long a,b,c,d,e,f,g,i,j,cc=1,t;

scanf("%lld",&t);

while(t--){

scanf("%lld %lld %lld %lld",&a,&b,&c,&d);

e=a*(c+1)+b*(d+1);

        f=(a+b)*(c+1+d);

        g=gcd(e,f);

        if(g>0){

        e/=g;

        f/=g;

        }

        if(e==0){

        printf("Case %lld: 0\n",cc);

        }else{

        printf("Case %lld: %lld/%lld\n",cc,e,f);

        }

        cc++;

}

return 0;

}

Rivals

problam statement is here

#include<stdio.h>

#define MOD 1000000007

long long ar[2000010];

void fact(){

long long i;

    ar[0]=1;

    ar[1]=1;

    for(i=2;i<=2000000;i++)

        ar[i]=(ar[i-1]*i)%MOD;

}

long long fermet(long long x){

    long long a=1,p=x,n=MOD-2;

    while(n){

        if(n&1)

            a=(a*p)%MOD;

        p=(p*p)%MOD;

        n>>=1;

    }

    return a;

}

int main(){

    int t,a,b;

    long long c,d;

    fact() ;

    scanf("%d",&t);

    while(t--){

        scanf("%d %d",&a,&b);

        c=(fermet(ar[a])*fermet(ar[b]))%MOD;

        d=(ar[a+b]*c)%MOD;

        printf("%lld\n",d);

    }

    return 0;

}

Balanced base-3

problem statement is here

#include<stdio.h>

int main() {

int t,y,z,n,ar[10000],i;

scanf("%d",&t);

while(t--){

scanf("%d",&n);

z=0;

while(n){

ar[z]=n%3;

z++;

n/=3;

}

ar[z]=0;

for(i=0;i<=z;i++){

if(ar[i]==2){

ar[i]=-1;

ar[i+1]++;

}else if(ar[i]==3){

ar[i]=0;

ar[i+1]++;

}

}

y=0;

for(i=z;i>=0;i--){

if(ar[i]!=0){

y=1;

if(ar[i]==1) 

printf("+");

else if(ar[i]==-1)

printf("-");

}

else if(y==1) 

printf("0");

}

printf("\n");

}

return 0;

}

Tulip And Numbers

problem statement is here

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

}
return 0;
}