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

Between the Mountains

problem statement is here

#include<stdio.h>

int main()

{

    long long int t,a,b,ar[1100],br[1100],x,h,k,p,i,j,ans,now;

    scanf("%lld",&t);

    while(t--)

    {

              now=0;

              ans=10000000;

              h=0;k=0;x=0;

              scanf("%lld",&a);

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

              scanf("%lld",&ar[i]);

              scanf("%lld",&b);

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

              scanf("%lld",&br[i]);

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

              {

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

                              {

                                              if(ar[i]==br[j])

                                              {

                                                              h=1;

                                                              ans=0;

                                                              break;

                                                              }else if(ar[i]>br[j]){

                                                                    now=ar[i]-br[j];

                                                                    }else{

                                                                          now=br[j]-ar[i];

                                                                          }

                                              ans=(ans<now)?ans:now;

                              }

                              if(h==1)

                              break;

              }

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

              }

              return 0;

    }

                                                              

Sometimes, a penalty is good!

problem statement is here


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

int main(){
    long long g,t,a,d,x,y,n,i,j,k,l;
    while(1){
             n=0;
             scanf("%lld %lld %lld %lld",&g,&t,&a,&d);
             if(g==-1&&t==-1&&a==-1&&d==-1)
             break;
             else{
                  n=g*((t*(t-1))/2);
                  k=g*a+d;
                  for(i=0;i<50 ;i++){
                           if(pow(2,i)==k){
                                           y=0;
                                           i--;
                                           break;
                                           }else if(pow(2,i)<k && pow(2,i+1)>k){
                                                 y=pow(2,i+1)-k;
                                                 break;
                                                 }
                           }
                  for(l=i;l>=0;l--){
                                    n+=pow(2,l);
                                    }
                  printf("%lld*%lld/%lld+%lld=%lld+%lld\n",g,a,t,d,n,y);
                  }
                  }
             return 0;
             }

What’s Next

problem statement is here

#include<stdio.h>
int main()
{
    int a,b,c,n,d,r,p,l;
    while(1)
    {
            scanf("%d %d %d",&a,&b,&c);
            if(a==0&&b==0&&c==0)
            break;
            else
            {
            l=(c-b)/(b-a);
            if(l==1)
            {
                    d=c-b;
                    n=c+d;
                    printf("AP %d\n",n);
                    }
                    else
                    {
                        r=c/b;
                        p=c*r;
                        printf("GP %d\n",p);
                        }
                        }
                        }
                        return 0;
                        }

abs(a-b) I

problem statement is here

#include<stdio.h>
int main(){
long long int a,b,ar[100000],i,j,u,p,t,sum;
scanf("%lld",&t);
while(t--){
sum=0;
scanf("%lld",&a);
scanf("%lld",&ar[0]);
u=0;
for(i=1;i<a;i++){
scanf("%lld",&ar[i]);
p=ar[i]-ar[i-1];
u+=(i*p);
sum+=u;
}
printf("%lld\n",sum);
}
return 0;
}

David and his Obsession

problem statement is here


#include<stdio.h>
int main(){
printf("1/420\n");
return 0;
}

A Summatory

problem statement is here

#include <stdio.h>

#define M 1000010

int t,c;

long long int sum[M];

int main(){

      long long int i, a = 0;

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

                  a = (a + i*i*i) % 1000000003;

                  sum[i] = (sum[i-1] + a) % 1000000003;

                   }

           scanf("%d", &t);

           while (t--){

              scanf("%d", &c);

              printf("%lld\n", sum[c]);

               }

           return 0;

}

GETTING AN AP

problem statement is here

#include<stdio.h>

long long gcd(long long m,long long n){

 if(n==0)

  return m;

 else 

  return gcd(n,m%n);

}

long long calcu(long long a,long long n){

long long u,c,d;

u=0;

if(n%2==0){

c=(a-n)/2;

c--;

d=(a-1)/2;

u=(d*(d+1))/2;

u=u-(c*(c+1))/2;

u*=2;

}else{

c=(a-n)/2;

c--;

d=(a-2)/2;

u=(d*(d+1))/2;

u=u-(c*(c+1))/2;

u*=2;

u+=((a-1)/2);

}

u+=n;

return u;

}

int main(){

long long a,b,n,p,t;

scanf("%lld",&t);

while(t--){

scanf("%lld",&n);

a=calcu(3*n,n)+calcu(n,n-2);

a-=(n-2);

p=n*2*n*3*n;

b=gcd(a,p);

a/=b;

p/=b;

printf("%lld/%lld\n",a,p);

}

return 0;

}

Large subsequence Problem

problem statement is here

#include<stdio.h>
#include<string.h>
#define mod 1000000007
int main(){
int c=1,i,n,t,u,v,s;
char ar[10011];
scanf("%d",&t);
while(t--){
s=0;
int br[11]={0};
scanf("%s",ar);
n=strlen(ar);
for(i=0;i<n;i++){
v=u=ar[i]-48;
while(v--){
br[u]=(br[u]+br[v])%mod;
}
br[u]++;
}
for(i=0;i<=9;i++){
s=(s+br[i])%mod;
}
printf("Case %d: %d\n",c,s);
c++;
}
return 0;
}

Distracted judges

problem statement is here

#include<stdio.h>

int main(){

long a,b,c,d,i,j,t,n;

scanf("%ld",&t);

long ar[100005],br[100005],cr[100005]={0};

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

scanf("%ld",&ar[i]);

}

j=0;

br[j]=t;

j++;

a=1;

for(i=t-2;i>=0;i--){

if(ar[i]==a){

br[j++]=i;

cr[i]=1;

}else if(cr[i+ar[i]+1]==1){

br[j++]=i;

cr[i]++;

}

a++;

}

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

if(br[i]!=0)

printf("%ld\n",br[i]);

}

return 0;

}

Gallantry

problem statement is here

#include<stdio.h>

#include<algorithm>

using namespace std;

int main(){

int a,b,c,d,ar[10004],br[10000],n,i,j,t;

scanf("%d",&t);

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

scanf("%d",&ar[i]);

}

sort(ar,ar+t);

b=0;c=0;

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

br[b]=ar[i+1]-ar[i];

c+=br[b];

b++;

}

if(c==0){

printf("-1\n");

}else{

a=t/2;d=0;n=0;

sort(br,br+a);

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

if(c-br[i]>n+br[i]){

c-=br[i];

d++;

n+=br[i];

}else{

break;

}

}

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

}

return 0;

}

Breadth first traversal for undirected graph

here we are assuming that all the nodes are connected


#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
void bfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  queue<int> que;
  visited[i]=1;
  que.push(i);
  while(que.size()>0){
   i=que.front();
   que.pop();
   printf("%d\n",i);
   for(j=0;j<ar[i].size();j++){
          if(visited[ar[i][j]]==0){
              que.push(ar[i][j]);
              visited[ar[i][j]]=1;
          }
      }
  }

}
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);
   printf("Enter edges\n");
   for(j=0;j<m;j++){
     scanf("%d %d",&a,&b);
     ar[a].push_back(b);
     ar[b].push_back(a);
   }
   printf("from which node to traverse\n");
   scanf("%d",&i);
   bfs(ar,visited,i,n);
  return 0;
}

Crucial Equation

problem statement is here

#include<stdio.h>

gcd(int m,int n){

if(n==0)

return m;

else 

return gcd(n,m%n);

}

int main(){

int a,b,c,t,g,e=1;

scanf("%d",&t);

while(t--){

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

g=gcd(abs(a),abs(b));

if(c%g==0)

printf("Case %d: Yes\n",e);

else 

printf("Case %d: No\n",e);

e++;

}

return 0;

}

Pigeonhole Tower

problem statement is here

#include<stdio.h>

#include<math.h>

int main() {

long long a,b,c=1,d,i,j,t,n;

scanf("%lld",&t);

while(t--){

scanf("%lld",&n);

if(n<3){

a=0;

}else{

b=sqrt(n);

while(1){

if(b*(b+2)<=n){

a=b;

break;

}else{

b--;

}

}

}

printf("Case %lld: %lld\n",c,a);

c++;

}

return 0;

}

spoj dota heroes

problem statement is here

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

Boring factorials

problem is here

This can be solved using Wilson theorem
   (1). if n>=p  ans would be 0
   (2). then we have to use Wilson's theorem
             (p-1)!   ≡  -1 (mod p)
             1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)
             n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)
             n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)


#include<stdio.h>
long long power(long long a,long long b,long long m){
  long long x=1,y=a;
  while(b>0){
  if(b%2!=0){
  x=(x*y)%m;
  }
  y=(y*y)%m;
  b>>=1;
  }
  return x;
}
int main(){
  int t;
  long long n,p,i,result,z,x;
  scanf("%d",&t);
  while(t--){
  result=-1;
  scanf("%lld %lld",&n,&p);
  if(n>=p){
    printf("0\n");
    continue;
  }
  x=1;
  for(i=n+1;i<p;i++){
  x=(x*i)%p;
  }
    z=power(x,p-2,p);
    result=(result*z)%p;
  printf("%lld\n",p+result);
  }
  return 0;

}

Interesting Selection

problem statement is here

here we have two possibilities
        (1). we take cold drink from 1st position
        (2). we take poison from 1st position
rest can be easily calculated using dp


#include<stdio.h>
long long ar[100006],br[100007];
long long max(long long a,long long b){
if(a>b){
return a;
}else{
return b;
}
}
long long check(long long a,long long b){

if(a>b){
return 0;
}
long long cr[b+1],i;
cr[a]=ar[a];
cr[a-1]=0;
for(i=a+1;i<=b;i++){
cr[i]=max((cr[i-2]+ar[i]-br[i-1]),cr[i-1]-br[i]);
}
return cr[b];
}
int main(){
long long a,b,c,i,j,n,x,y,z;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<n;i++){
scanf("%lld",&br[i]);
}
if(n==1){
x=ar[0];
}else if(n==2){
x=max(ar[0]-br[1],ar[1]-br[0]);
}else{
y=ar[0]-br[n-1]-br[1]+check(2,n-2);
z=check(1,n-1)-br[0];
x=max(y,z);
}
printf("%lld\n",x);
}
return 0;
}