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

D - Playing with Marbles

problem statement is here

#include<stdio.h>
int main()
{
    long long int s,n,j,x;
    while (1)
    {
                    s=0;
                    scanf("%lld",&n);
                    if(n==0)
                    break;
                    else
                    {
                        x=n+1;
                        s=(3*x*x-x)/2;
                                     }
                                     printf("%lld\n",s);
                                     }
                                     return 0;
                                     }

Board

problem statement is here

#include <stdio.h>

long long int dp[10010]={0};
int t,n;

long long int min(long long int a,long long int b){
return a > b ? b : a;
}

int main(){
int i, h,j,z,m;
long long int ar[10000],sum=0,min=100000000;
scanf("%d", &t);
scanf("%d",&z);
for(i=1;i<t;i++){
scanf("%lld",&ar[i]);
sum+=ar[i];
}
for(i=1;i<t;i++){
m=i;
for(j=1;j<=z;j++){
if(m>=1){
if(dp[m-1]<min){
min=dp[m-1];
}
m--;
}
}
dp[i]=min+ar[i];
min=100000000;
}
for(j=1;j<=z;j++){
if(dp[t-j]<min){
min=dp[t-j];
}
}
sum-=min;
printf("%lld\n",sum);
return 0;
}

Atoms in the Lab

problem statement is here

#include <stdio.h>
 int main(){
    int p;
    long long n,k,m,count;
    double mul;
    scanf("%d",&p);
    while(p--){
        scanf("%lld %lld %lld",&n,&k,&m);
        mul=n;
        count=0;
        while(mul<=m){
            count++;
            mul*=k;
        }
        if (count>0)
            printf("%lld\n",count-1);
        else
            printf("0\n");
    }

    return 0;
}

MayanCalendar

problem statement is here

#include<stdio.h>

int main()

{

        long long int t,i,month,year1,year2,x,y,total_days,u,a,b,c,d,e;

        scanf("%lld",&t);

        while(t--)

        {

                int arr[13];

                arr[1]=31,arr[2]=28,arr[3]=31,arr[4]=30,arr[5]=31,arr[6]=30,arr[7]=31,arr[8]=31,arr[9]=30,arr[10]=31,arr[11]=30,arr[12]=31;

                total_days=0;

                scanf("%lld %lld",&year1,&year2);

                y=1901;

                month=12;i=0;

                if(year1>1901){

                        while(y<year1){

                    if((y%4==0&&y%100!=0)||y%400==0){

                                total_days+=366;

                        }else{

                                total_days+=365;

                        }

                        y=y+1;

                        }

                }

                    u=0;

                        i=total_days%7;

                        total_days=i; 

                        if(i==4){

                        u++;

                        }

                        for(x=year1;x<=year2;x++){

                        for(y=1;y<=12;y++){

                        if(x==year2 && y==12)

                        break;

                        if(y==2){

                                if((x%4==0&&x%100!=0)||x%400==0){

                                total_days+=29;

                                }else{

                                total_days+=28;

                                }

                                }else

                                total_days+=arr[y];

                                if(total_days%7==4){

                                u++;

                                }

                            }

                           

                        }

                        total_days=total_days+31-i-u;

                        a=total_days/144000;

                        total_days-=(a*144000);

                         b=total_days/7200;

                        total_days-=(b*7200);

                         c=total_days/360;

                        total_days-=(c*360);

                         d=total_days/20;

                        total_days-=(d*20);

                        e=total_days;

                        printf("%lld.%lld.%lld.%lld.%lld\n",a,b,c,d,e);

        }

        return 0;

}

Tiles of Tetris, Not!

problem statement is here

#include<stdio.h>
int main(){
    long long int a,b,n,p;
    while(1){
             scanf("%lld %lld",&a,&b);
             if(a==0 && b==0)
             break;
             if(a>b){
                     if(a%b==0)
                     printf("%lld\n",a/b);
                     else
                     printf("%lld\n",a*b);
                     }else{
                           if(b%a==0)
                     printf("%lld\n",b/a);
                     else
                     printf("%lld\n",a*b);
                     }
                     }
             return 0;
             }

What is your Logo

problem statement is here

#include<cstdio>
using namespace std;
int main(){
int a,b,c,i,j,u,v,ans;
char br[1100];
bool ar[2002][2002];
while(1){

scanf("%s",br);
if(br[0]=='Q')
break;
for(i=0;i<2002;i++){
for(j=0;j<2002;j++){
ar[i][j]=false;
}
}
u=1001;v=1001;ans=0;
for(i=0;br[i]!='Q';i++){
ar[u][v]=true;
if(br[i]=='U'){
u--;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='D'){
u++;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='R'){
v++;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='L'){
v--;
if(ar[u][v]==1){
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}

Think I will Buy Me a Football Team

problem statement is here

#include <stdio.h>
int b[10000];
int main(){
    long long int n,i,j,sum,z,c=1;
    while(1){
scanf("%lld",&n);
if(n==0)
break;
        sum = 0;
        for(i=0;i<n;i++)
b[i] = 0;
        for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%lld", &z);
            if(z){
                b[j]+=z;
                b[i]-=z;
                sum+=z;
            }
            }
        }
        printf("%lld. %lld ",c,sum);
        sum = 0;
        for(i=0;i<n;i++){
if(b[i] > 0)
sum += b[i];
}
        printf("%lld\n", sum);
        c++;
    }
    return 0;
}

Saruman of Many Colours

problem statement is here

#include<stdio.h>

#include<string.h>

int main(){

long int a,b,t,i,j,sum,n,u,k;

scanf("%ld",&t);

while(t--){

j=1;

sum=0;b=0;u=0;

char ar[25000];

scanf("%ld %ld",&n,&k);

scanf("%s",ar);

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

if(ar[i]>96 && ar[i]<123){

if(ar[i]==u){

b++;

if(b==k){

j=0;

b=0;

u=0;

}

}else{

sum++;

u=ar[i];

b=1;

if(b==k){

j=0;

b=0;

u=0;

}

}

}

}

if(j==1){

printf("-1\n");

}else{

printf("%ld\n",sum);

}

}

return 0;

}

The Glittering Caves of Aglarond

problem statement is here

#include<stdio.h>

int main(){

    int a,b,t,x,n,m,k,i,j,min,h;
    char arr[55];
    scanf("%d",&t);
    while(t--){
               int ar[55]={0};
               scanf("%d %d %d",&n,&m,&k);
               for(i=0;i<n;i++){
                                scanf("%s",arr);
                                for(h=0;h<m;h++){
                                           if(arr[h]=='*')
                                           ar[i]++;
                                           }
                                }
               for(j=0;j<k;j++){
                                min=ar[0];
                                a=0;
                                for(i=1;i<n;i++){
                                                 if(ar[i]<min){
                                                 min=ar[i];
                                                 a=i;
                                                 }
                                                 }
                                ar[a]=m-min;
                                }
               int ans=0;
               for(i=0;i<n;i++){
                                ans+=ar[i];
                                }
               printf("%d\n",ans);
               }
       return 0;
               }
   

The Mirror of Galadriel

problem statement is here

#include<stdio.h>

int main()

{

    int t,i,count,j,l;

    char a[11];

    scanf("%d",&t);

    for(i=0;i<t;i++)

    {

                    count=0;

                    scanf("%s",a);

                    l=strlen(a);

                              for(j=0;j<l;j++)

                              {

                                              if(a[j]!=a[l-1-j])

                                              count=1;

                                              }

                                              if(count==1)

                                              printf("NO\n");

                                              else

                                              printf("YES\n");

                                              }

                                              return 0;

                                              }

Gandalf vs the Balrog

problem statement is here

#include<stdio.h>

int main(){

int t,i,j,f,p,q;

scanf("%d",&t);

while(t--){

int n,m;

f=0;

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

if(m==0)

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

else{

int ar[n];

for(i=0;i<=n-1;i++)

ar[i]=i;

for(i=0;i<=m-1;i++){

scanf("%d%d",&p,&q);

ar[p-1]+=1;

ar[q-1]-=1;

}

for(i=n-1;i>=0;i--){

if(ar[i]==n-1){

j=i;

f=1;

break;

}

}

if(f==1)

printf("2 %d\n",j+1);

else

printf("1\n");

 

}

}

return 0;

}

 

Alice Sieve

problem statement is here

#include<stdio.h>
int main(){
    long a,t;
    scanf("%ld",&t);
    while(t--){
               scanf("%ld",&a);
               printf("%ld\n",(a+1)/2);
               }
    return 0;
}

How to Handle the Fans

problem statement is here

#include<stdio.h>
#include<string.h>
long long n,br[1000000]={0};
long long int add(long long i,long long b){
while(i<=n){
br[i]+=b;
i=i+(i&((-1)*i));
}
}
long long find(long long i){
long long s=0;
while(i>0){
s+=br[i];
i=i-(i&((-1)*i));
}
return s;
}
int main(){
char ar[100];
long long a,b,c,d,i,j,t,u=0,ans,q;
scanf("%lld %lld",&n,&q);
while(q--){
scanf("%s %lld %lld",ar,&a,&b);
if(ar[0]=='a'){
add(a,b);
}else if(ar[0]=='f'){
if(a>1)
d=find(b)-find(a-1);
else
d=find(b);
printf("%lld\n",d);
}
}
return 0;
}

Adding Reversed Numbers

problem statement is here

#include<stdio.h>
int main()
{
      int a,n,i,m,j,p,o,t,s,c,l;
      scanf("%d",&a);
      int ar[a];
      for(i=0;i<a;i++)
      {
                      c=0;s=0;j=0;
                      scanf("%d %d",&n,&m);
                      while(n!=0)
                      {
                                 p=n%10;
                                 c=c*10+p;
                                 n=n/10;
                                 }
                                 while(m!=0)
                      {
                                 o=m%10;
                                 s=s*10+o;
                                 m=m/10;
                                 }
                                 t=s+c;
                                 while(t!=0)
                                 {
                                            l=t%10;
                                            j=j*10+l;
                                            t=t/10;
                                           
                                            }
                                            printf("%d\n",j);
                                           
                                            }
                                           
                                       
                                           
                                            return 0;
                                            }
                               

Alpha Centauri Tennis

problem statement is here

#include<stdio.h>
#include<string.h>
int main(){
        int t;
        scanf("%d",&t);
        while (t--)
        {
                int n;
                char s[500000];
                scanf("%d %s",&n,s);
                printf("%c\n",s[strlen(s)-1]);
        }
        return 0;
}