Thursday, December 15, 2016

1043 - Triangle Partitioning

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1043

Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{

    double ab,ac,bc,r;
    int t;
    double ans;
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        cin>>ab>>ac>>bc>>r;

        r=(1/r)+1;

        ab=ab*ab;

        ans=sqrt(ab/r);
        printf("Case %d: %f\n",ca,ans);
    }


}

1253 - Misere Nim

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1253

Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a[103];

    int t,k,ans,ok;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d",&k);

        for(int i=1;i<=k;i++)
        {
            scanf("%d",&a[i]);
        }
            ok=0;

           for(int i=1;i<=k;i++)
           {
               if(a[i]==1) ok=1;
               else
               {
                   ok=0;
                   break;
               }
           }
           ans=0;
           for(int i=1;i<=k;i++)
           {
               ans=ans xor a[i];
           }

                if(ok==1 and (k%2!=0)) printf("Case %d: Bob\n",ca);
                else if(ok==1 and (k%2==0)) printf("Case %d: Alice\n",ca);
                else if(ans==0) printf("Case %d: Bob\n",ca);
                else printf("Case %d: Alice\n",ca);
        }

    }


Wednesday, December 14, 2016

1247 - Matrix Game

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1247

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<int>v;

int main()
{
    int t,m,n,sum,ans,a;

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&m,&n);

        for(int i=1; i<=m; i++)
        {
            sum=0;
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&a);
                sum=sum+a;
            }
            v.push_back(sum);
        }

        ans=0;

        for(int i=0; i<v.size(); i++)
        {
            ans=ans xor v[i];
        }

        if(ans==0) printf("Case %d: Bob\n",ca);
        else printf("Case %d: Alice\n",ca);

        v.clear();
    }
}

1186 - Incredible Chess

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1186

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<int>v;

int main()
{
    int t,n,ans;

    int a[103],b[103];

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d",&n);

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);

        for(int i=1;i<=n;i++) v.push_back(b[i]-a[i]-1);

        ans=0;

        for(int i=0;i<v.size();i++) ans=ans xor v[i];

        if(ans==0) printf("Case %d: black wins\n",ca);
        else printf("Case %d: white wins\n",ca);

        v.clear();

    }

}

1192 - Left Right

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1192

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<int>v;

int main()
{
    int t,k,a,b,ans;
    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d",&k);

        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&a,&b);
            v.push_back(b-a-1);
        }
        ans=0;
        for(int i=0;i<v.size();i++)
        {
            ans=ans xor v[i];
        }

        if(ans==0) printf("Case %d: Bob\n",ca);
        else printf("Case %d: Alice\n",ca);
        v.clear();
    }
}


Monday, November 14, 2016

1241 - Pinocchio

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1241

Solution :

#include<bits/stdc++.h>
using namespace std;


int main()
{

    int t;
    scanf("%d",&t);

    int n,a,cnt,b,c;

    for(int ca=1; ca<=t; ca++)
    {
        cnt=0;
        a=-1;
        b=2;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            c=a-b;

            cnt=cnt+(c/5);
            if((c%5)!=0) cnt++;

            b=a;

        }
        printf("Case %d: %d\n",ca,cnt);
    }


}

1225 - Palindromic Numbers (II)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1225

Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t,l,m,cnt;
    char s[20];

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
       scanf("%s",s);
       l=strlen(s);

       if(l%2==0) m=l/2;
       else m=(l/2)+1;
       cnt =1;

       for(int i=0;i<m;i++)
       {
          if(s[i]==s[l-i-1]);
          else
          {
              cnt=0;
              break;
          }
       }

       if(cnt==0) printf("Case %d: No\n",ca);
       else printf("Case %d: Yes\n",ca);

    }
}

1166 - Old Sorting

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1166

Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{

    int t;
    int n,a,b,c;
    int cnt,mnt,ans,m;
    int ara[102];

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d",&n);

        m=n,cnt=0,mnt=0,ans=0;

        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            ara[i]=a;
        }


        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(ara[j]==i and j!=i)
                {

                    ara[j]=ara[i];
                    ara[i]=i;
                    cnt++;
                }
            }

        }

        printf("Case %d: %d\n",ca,cnt);
    }
}

Monday, November 7, 2016

1141 - Number Transformation

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1141

Solution :

#include<bits/stdc++.h>

using namespace std;

bool status[1021];

vector<int>factor;
vector< int>prime;

void sieve()
{
    int n=1020;
    int sq=sqrt(n);

    for( int i=4; i<=n; i=i+2) status[i]=true;

    prime.push_back(2);

    for( int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    for( int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

int visited[1020];

int bfs(int s,int d)
{
    int u,p;
    memset(visited,-1,sizeof(visited));

    queue<int>q;

    q.push(s);
    visited[s]=0;

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; prime[i]<u; i++)
        {
            if(u%prime[i]==0)
            {
                factor.push_back(prime[i]);
            }
        }


        for(int i=0; i<factor.size(); i++)
        {
            p=u+factor[i];

            if(visited[p]==-1 and p<=d)
            {
                visited[p]=visited[u]+1;
                q.push(p);

            }
        }
        factor.clear();
    }
    return visited[d];


}

int main()
{
    int t,a,b,ans;
    sieve();
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&a,&b);
        ans=bfs(a,b);
        printf("Case %d: %d\n",ca,ans);
        factor.clear();
    }
}

1433 - Minimum Arc Distance

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1433

Solution :

#include<bits/stdc++.h>

#define PI acos(-1.0)

using namespace std;

double cosinv(double angle)
{
    return acos(angle)*(180/PI);
}

int main()
{
    int t;
    scanf("%d",&t);

    double ox,oy,ax,ay,bx,by,r,s,angle,a;

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%lf%lf%lf%lf%lf%lf",&ox,&oy,&ax,&ay,&bx,&by);

        r=sqrt(((ox-ax)*(ox-ax))+((oy-ay)*(oy-ay)));
        a=sqrt(((ax-bx)*(ax-bx))+((ay-by)*(ay-by)));

        angle=(2*(r*r)-(a*a))/(2*r*r);
        angle=cosinv(angle);
        angle=(angle*PI)/180;

        s=r*angle;

        printf("Case %d: %f\n",ca,s);
    }
}

1331 - Agent J

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1331

Solution

#include<bits/stdc++.h>

#define PI acos(-1.0)

using namespace std;

double cosinv(double angle)
{
    return acos(angle)*(180/PI);
}

int main()
{
    int t;
    scanf("%d",&t);

    double r1,r2,r3,area,a1,a2,a3,t1,t2,t3;

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%lf%lf%lf",&r1,&r2,&r3);

        t1=((r1+r2)*(r1+r2))+((r1+r3)*(r1+r3))-((r2+r3)*(r2+r3));
        t1=t1/(2*(r1+r2)*(r1+r3));
        t1=cosinv(t1);

        t2=((r1+r2)*(r1+r2))+((r2+r3)*(r2+r3))-((r1+r3)*(r1+r3));
        t2=t2/(2*((r1+r2))*(r2+r3));
        t2=cosinv(t2);

        t3=((r1+r3)*(r1+r3))+((r2+r3)*(r2+r3))-((r1+r2)*(r1+r2));
        t3=t3/(2*((r1+r3)*(r2+r3)));
        t3=cosinv(t3);

        a1=PI*(r1*r1)*(t1/360);
        a2=PI*(r2*r2)*(t2/360);
        a3=PI*(r3*r3)*(t3/360);

        area=.5*(r1+r2)*(r2+r3)*sin(t2*PI/180);
        area=area-a1-a2-a3;

        printf("Case %d: %f\n",ca,area);
    }

}

Saturday, November 5, 2016

1311 - Unlucky Bird

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1311

Solution

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    double v1,v2,v3,a1,a2,t1,t2,d,ans,s1,s2;

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%lf%lf%lf%lf%lf",&v1,&v2,&v3,&a1,&a2);

        s1=(v1*v1)/(2.0*a1);
        s2=(v2*v2)/(2.0*a2);

        d=s1+s2;

        t1=v1/a1;
        t2=v2/a2;

        t1=max(t1,t2);

        ans=v3*t1;

        printf("Case %d: %f %f\n",ca,d,ans);

    }

}

Friday, November 4, 2016

1337 - The Crystal Maze

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1337

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[502][502];
int dell[502][502];
int visited[502][502];


int fx[]= {1,-1,0,0};
int fy[]= {0,0,1,-1};

int r,c,ok=1;

map<int,int>mp;

int bfs(pii s)
{
    visited[s.first][s.second]=1;
    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    if(cell[s.first][s.second]==3) cnt++;
    dell[s.first][s.second]=ok;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=1 and x<=r and y>=1 and y<=c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                dell[x][y]=ok;
                if(cell[x][y]==3) cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    mp[ok]=cnt;
    return cnt;

}

int main()
{
    int t,ans,q,a,b;
    char ch;
    pii s,s1,s2,d;
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d%d",&r,&c,&q);
        getchar();
        memset(dell,-1,sizeof(dell));
        memset(visited,0,sizeof(visited));
        ok=1;
        for(int i=1; i<=r; i++)
        {
            for(int j=1; j<=c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else if(ch=='C')
                {
                    cell[i][j]=3;

                }
            }
            getchar();
        }
        printf("Case %d:\n",ca);
        for(int i=0; i<q; i++)
        {
            scanf("%d%d",&a,&b);

            s.first=a;
            s.second=b;
            if(visited[a][b]!=0) printf("%d\n",mp[dell[a][b]]);
            else
            {
                ans= bfs(s);
                printf("%d\n",ans);
            }
            ok++;
        }

        mp.clear();

    }

}

Wednesday, November 2, 2016

1020 - A Childhood Game

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1020

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    string a;
    ll int n,ok;

    int t;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        cin>>n>>a;

        ok=0;

        if(a=="Alice")
        {
            if((n-1)%3==0)
            {
                ok=1;
            }
            else ok=0;
        }
        else
        {
        if(n%3==0) ok=0;
        else ok=1;
        }

        if(ok==1) printf("Case %d: Bob\n",ca);
        else printf("Case %d: Alice\n",ca);
    }


}

Monday, October 24, 2016

1238 - Power Puff Girls

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1238

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[22][22];
int visited[22][22];
int dis[22][22];

int fx[]= {1,-1,0,0};
int fy[]= {0,0,1,-1};

int r,c;

int bfs(pii s,pii d)
{
    memset(visited,0,sizeof(visited));

    memset(dis,0,sizeof(dis));

    visited[s.first][s.second]=1;
    dis[s.first][s.second]=0;

    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=0 and x<r and y>=0 and y<c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                dis[x][y]=dis[u.first][u.second]+1;
                cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    return dis[d.first][d.second];

}

int main()
{
    int t,ans;
    char ch;
    pii s,s1,s2,d;
    scanf("%d",&t);


    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&r,&c);
        getchar();
        memset(cell,-1,sizeof(cell));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else if(ch=='c')
                {
                    cell[i][j]=3;
                    s1.first=i;
                    s1.second=j;
                }
                else if(ch=='a')
                {
                    cell[i][j]=4;
                    s2.first=i;
                    s2.second=j;
                }
                else if(ch=='b')
                {

                    cell[i][j]=5;
                    s.first=i;
                    s.second=j;
                }
                else if(ch=='h')
                {
                    cell[i][j]=6;
                    d.first=i;
                    d.second=j;
                }
                else
                {
                    cell[i][j]=2;
                }

            }
            getchar();
        }

        ans=bfs(s,d);
        ans=max(ans,bfs(s1,d));
        ans=max(ans,bfs(s2,d));

        printf("Case %d: %d\n",ca,ans);
    }

}

1257 - Farthest Nodes in a Tree (II)

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1257

Solution :


#include<bits/stdc++.h>
#define inf 1e9
#define ll long long

using namespace std;

vector<ll int> v[30005],cost[30005];

ll int dis[30005];
ll int dis1[30005];
ll int n;



struct node
{
    ll int city,dist;

    node(ll int a,ll int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void func(ll int s)
{

    for(ll int i=0; i<30005; i++) dis1[i]=inf;

    ll int mx=-1,p;

    dis1[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis1[p]>(dis1[u]+cost[u][i]))
            {
                dis1[p]=(dis1[u]+cost[u][i]);
                q.push(node(p,dis1[p]));

            }
        }
    }



}
ll int dijkstra(ll int s)
{

    for(ll int i=0; i<30005; i++) dis[i]=inf;

    ll int mx=-1,p;

    dis[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis[p]>(dis[u]+cost[u][i]))
            {
                dis[p]=(dis[u]+cost[u][i]);
                q.push(node(p,dis[p]));

            }
        }
    }
    for(ll int i=0; i<n; i++)
    {
        if(dis[i]>mx)
        {
            mx=dis[i];
            p=i;
        }
    }


    return p;


}
int main()
{


    ll int t,a,b,c,ans=0,s=0,mx;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        s=0,mx=-1,ans=0;


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

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



            v[a].push_back(b);
            v[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);

        }


        ans=dijkstra(1);
        ans=dijkstra(ans);
        func(ans);

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

       for(int i=0;i<n;i++)
       {
           printf("%lld\n",max(dis[i],dis1[i]));
       }


        for(ll int i=0; i<30005; i++)
        {
            v[i].clear();
            cost[i].clear();
        }

    }

}

Friday, October 21, 2016

1094 - Farthest Nodes in a Tree

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1094

Solution :


#include<bits/stdc++.h>
#define inf 1e9
#define ll long long

using namespace std;

vector<ll int> v[30005],cost[30005];

ll int dis[30005];
ll int n;



struct node
{
    ll int city,dist;

    node(ll int a,ll int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

ll int dijkstra(ll int s)
{

    for(ll int i=0; i<30005; i++) dis[i]=inf;

    ll int mx=-1,p;

    dis[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis[p]>(dis[u]+cost[u][i]))
            {
                dis[p]=(dis[u]+cost[u][i]);
                q.push(node(p,dis[p]));

            }
        }
    }
    for(ll int i=0; i<n; i++)
    {
        if(dis[i]>mx)
        {
            mx=dis[i];
            p=i;
        }
    }


    return p;


}
int main()
{


    ll int t,a,b,c,ans=0,s=0,mx;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        s=0,mx=-1,ans=0;


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

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



            v[a].push_back(b);
            v[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);

        }


        ans=dijkstra(1);
        ans=dijkstra(ans);
        ans=dis[ans];



        printf("Case %lld: %lld\n",ca,ans);


        for(ll int i=0; i<30005; i++)
        {
            v[i].clear();
            cost[i].clear();
        }

    }
}


1012 - Guilty Prince

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1012

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[21][21];
int visited[21][21];

int fx[]= {1,-1,0,0};
int fy[]={0,0,1,-1};

int r,c;

int bfs(pii s)
{
    memset(visited,0,sizeof(visited));

    visited[s.first][s.second]=1;

    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=0 and x<r and y>=0 and y<c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    return cnt+1;
}

int main()
{
    int t,ans;
    char ch;
    pii s;
    scanf("%d",&t);


    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&c,&r);
        getchar();
        memset(cell,-1,sizeof(cell));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else
                {
                    cell[i][j]=3;
                    s.first=i;
                    s.second=j;
                }

            }
            getchar();
        }

        ans=bfs(s);

        printf("Case %d: %d\n",ca,ans);
    }
}

Tuesday, October 18, 2016

1009 - Back to Underworld

Problem Linkhttp://www.lightoj.com/volume_showproblem.php?problem=1009

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<int>v[200001];
vector<int>node;

int visited[200001],cnt,mnt;

map<int,string>mp;
map<int,string> :: iterator it;

void bfs(int source)
{

    cnt=0,mnt=0;

    queue<int>q;

    q.push(source);

    visited[source]=0;
    cnt++;

    int u,p;

    while(!q.empty())
    {
        u=q.front();

        if(mp[u]=="black" and visited[u]==-1) cnt++;
        else if(mp[u]=="red" and visited[u]==-1) mnt++;

        q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];

            if(visited[p]==-1)
            {
                if(mp[u]=="black") mp[p]="red",mnt++;
                else mp[p]="black",cnt++;

                visited[p]=visited[u]+1;
                q.push(p);
            }

        }
    }
}

int main()
{

    int t,e,a,b,ans;
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d",&e);

        cnt=0,mnt=0,ans=0;

        for(int i=1; i<=e; i++)
        {


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

            v[a].push_back(b);
            v[b].push_back(a);

            node.push_back(a);
            node.push_back(b);

            mp[a]="black";
            mp[b]="black";
        }
        memset(visited,-1,sizeof(visited));

        for(int i=0; i<node.size(); i++)
        {
            if(visited[node[i]]==-1)
            {
                bfs(node[i]);
                ans=ans+max(cnt,mnt);
            }
        }

        printf("Case %d: %d\n",ca,ans);

        for(int i=0; i<200001; i++) v[i].clear();

        mp.clear();
        node.clear();

    }

}

Monday, October 17, 2016

1174 - Commandos

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1174

Solution:

#include<bits/stdc++.h>
#define inf 1000000

using namespace std;


int dis [101][101];


int main()
{


    int n,e,t;
    int a,b,c;
    int s,d,w;

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {

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

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if (i==j)
                {
                    dis[i][j]=0;
                }
                else
                {
                    dis[i][j]=inf;
                }
            }
        }





        for(int i=0; i<e; i++)
        {
            scanf("%d%d",&a,&b);

            dis[a][b]=1;
            dis[b][a]=1;


        }

        for(int k=0; k<n; k++)

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

                for(int j=0; j<n; j++)
                {
                    if(dis[i][j]>dis[i][k]+dis[k][j])
                    {
                        dis[i][j]=dis[i][k]+dis[k][j];

                    }
                }


        w=1;
        if(e==0) w=0;
        scanf("%d%d",&s,&d);

        for(int i=0; i<n; i++)
        {
            if(s!=i and d!=i) w=max(w,dis[s][i]+dis[i][d]);
        }



        printf("Case %d: %d\n",ca,w);
    }
}

1002 - Country Roads

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1002

Solution :

#include<bits/stdc++.h>
#define inf 100000

using namespace std;

vector<int> v[600],cost[600];

int dis[600];


struct node
{
    int city,dist;

    node(int a,int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void dijkstra(int s)
{

    for(int i=0;i<600;i++) dis[i]=inf;

    dis[s]=0;

    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

       node t=q.top();
        q.pop();

        int u=t.city;

        for(int i=0;i<v[u].size();i++)
        {
            int p=v[u][i];

            if(dis[p]>max(dis[u],cost[u][i]))
            {
                dis[p]=min(dis[p],max(dis[u],cost[u][i]));
                q.push(node(p,dis[p]));

            }
        }
    }

}

int main()
{



    int n,e,t,a,b,c,s;
    scanf("%d",&t);

for(int ca=1;ca<=t;ca++)

  {

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


    for(int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&a,&b,&c);

        v[a].push_back(b);
        v[b].push_back(a);
        cost[a].push_back(c);
        cost[b].push_back(c);
    }

    scanf("%d",&s);



    dijkstra(s);

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

    for(int i=0;i<n;i++)
    {
        if(dis[i]==inf) printf("Impossible\n");
        else printf("%d\n",dis[i]);
    }

    for(int i=0;i<600;i++)
    {
        v[i].clear();
        cost[i].clear();
    }

  }

}

Wednesday, September 28, 2016

solving linear equation by matrix normalization method

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a[4],b[4],c[4],e[4];

    char buff[10];

    string str;

    int m=1,n=1,l=1,k=1,h=0,d=0;
    int flag=0;

    for(int i=0; i<3; i++)
    {
        getline(cin,str);

        d=0,flag=0;

        for(int j=0; j<str.size(); j++)
        {
            if(str[j]=='-') flag=1;

            else if(str[j]>='0' and str[j]<='9') buff[d++]=str[j];

            else if(str[j]=='=' or str[j]=='+' or str[j]==' ') continue;

            else if(str[j]=='x')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                a[m++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;

            }
            else if(str[j]=='y')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                b[n++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;

            }
            else if(str[j]=='z')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                c[l++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;
            }

        }
        buff[d++]=NULL;
        h=atoi(buff);


        if(flag==1) h=-h;

        e[k++]=h;

        memset(buff,NULL,sizeof(buff));
        d=0;
        flag=0;
    }

    double a11,a12,a13,a21,a22,a23,a31,a32,a33,x1,x2,x3,c1,c2,c3,y1,y2,y3;

    a11=a[1],a21=a[2],a31=a[3];
    a12=b[1],a22=b[2],a32=b[3];
    a13=c[1],a23=c[2],a33=c[3];

    c1=e[1],c2=e[2],c3=e[3];


    double l21,l31,l32,u11,u12,u13,u22,u23,u33;

    u11=a11;
    u12=a12;
    u13=a13;

    l21=a21/u11;

    u22=a22-(l21*u12);

    u23=a23-(l21*u13);

    l31=a31/u11;

    l32=(a32-(l31*u12))/u22;

    u33=a33-(l31*u13)-(l32*u23);

    y1=c1;

    y2=c2-(l21*y1);

    y3=c3-(l31*y1)-(l32*y2);

    x3=(y3/u33);

    x2=(y2-(u23*x3))/u22;

    x1=(y1-((u12*x2)+(u13*x3)))/u11;

    cout<<x1<<endl<<x2<<endl<<x3;
}

Saturday, September 24, 2016

1258 - Making Huge Palindromes

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1258

Solution idea :

Consider the 4th test case
P = anncbaaababaaa
Let
Q = aaababaaabcnna (reverse of P)
Now look how can we construct the shortest palindrome by adding character to the
right of P,
with the help of Q
P : anncbaaababaaa|||||
Q : |||||aaababaaabcnna
Ans:anncbaaababaaabcnna
So all we need to do is search for the longest prefix of Q in P.
You can do this by using KMP.

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000002];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

int kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {

            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return j;
}


int main()
{

string text,pattern;

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

 for(int ca=1;ca<=n;ca++)
 {
     cin>>text;

     pattern=text;
     reverse(pattern.begin(),pattern.end());
     memset(f,0,sizeof(f));
    kmp_preprocess(pattern);

     p=kmp(text,pattern);
     q=pattern.size();
     q=2*q - p ;
     printf("Case %d: %d\n",ca,q);
 }


}


Wednesday, September 21, 2016

1255 - Substring Frequency / kmp source code 2


Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1255

Solve :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int f[1000003];

void kmp_preprocess(string pattern)
{
    ll int m=pattern.size();
    f[0]=0;

    ll int j=0;

    for(ll int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

ll int  kmp(string text,string pattern)
{
   ll int j=0,cnt=0;

    ll int n=text.size();
    ll int m=pattern.size();

    for(ll int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            j++;
            if(j==m)
            {
                cnt++;
                j=f[j-1];
            }

        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return cnt;
}


int main()
{
   string text,pattern;
   ll int t,n=0;
   scanf("%lld",&t);

for(ll int ca=1;ca<=t;ca++)
{
      cin>>text>>pattern;
      memset(f,0,sizeof(f));
      kmp_preprocess(pattern);
      n=kmp(text,pattern);
      printf("Case %lld: %lld\n",ca,n);

}

}

Saturday, September 10, 2016

10679 - I Love Strings!!

Problem Linkhttps://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{

   int k,q;

   scanf("%d",&k);
   string text,pattern;

   while(k--)
   {
      cin>>text;

       scanf("%d",&q);

       while(q--)
       {
           cin>>pattern;
           kmp_preprocess(pattern);

            bool n;

          n=kmp(text,pattern);

          if(n==1) cout<<"y"<<endl;
          else cout<<"n"<<endl;

       }
   }


}

KMP source code 1

Tutorial :

1. https://tanvir002700.wordpress.com/2015/03/03/kmp-knuth-morris-pratt-algorithm/#more-556

2. https://returnzerooo.wordpress.com/2016/09/08/kmp/

3. https://www.youtube.com/watch?v=GTJr8OvyEVQ

4. https://www.youtube.com/watch?v=KG44VoDtsAA



source code :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{
   string text,pattern;

   cin>>text>>pattern;

    kmp_preprocess(pattern);

    bool n;

    n=kmp(text,pattern);

    cout<<n;

}

Friday, July 15, 2016

1289 - LCM from 1 to n

Problem link : http://lightoj.com/volume_showproblem.php?problem=1289

Tutorialhttps://nlognblog.wordpress.com/2015/12/01/light-oj1289-lcm-from-1-to-n/

Hint
  1. When a problem says that you have to do modulo 2^32 (and it requires only addition, subtraction and multiplication) then just take them as unsigned integers and do regular operations. Just think that the compiler uses 32 bit operations, and if it overflows, then the most significant bits will be lost but the least significant 32 bits will be correct, which is equivalent to modulo 2^32.

Solution :

#include <bits/stdc++.h>
#define ll  unsigned

using namespace std;

const int MAX = 100000000;  // 10^8
const int LMT =     10000;  // sqrt(MAX)

int _c[(MAX>>6)+1];

int  primes[5761482];

#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))

#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))
ll mnt=0;
void sieve()
{
    int x=0;

    for (int i = 3; i <= LMT; i += 2)
        if (!IsComp(i))
            for (int j = i*i; j <= MAX; j += i+i)
                SetComp(j);

    primes[x++]=2;
    mnt++;
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
        {
            primes[x++]=i;
            mnt++;
        }
}

ll store[5761482];

void precal()
{
    store[0]=2;

    for(ll i=1; i<mnt; i++)
    {
        store[i]=store[i-1]*primes[i];
    }
}
ll cal(ll n)
{
    ll temp,ret=1;

    for(ll i=0; primes[i]*primes[i]<=n; i++)
    {
        temp=n;
        temp=temp/primes[i];
        while(temp>=primes[i])
        {
            temp=temp/primes[i];
            ret=ret*primes[i];
        }
    }
    return ret;

}

int main()
{
    ll  n,val,sq,q,rs,cnt,ans,t,ca=1;
    sieve();
    precal();
    scanf("%u",&t);

    while(t--)
    {
        scanf("%u",&n);

        ans=cal(n);

        val=upper_bound(primes,primes+mnt,n)-primes;
        val--;
        ans=ans*store[val];

        printf("Case %u: %u\n",ca,ans);
        ca++;
    }
}

Thursday, July 14, 2016

10680 - LCM

Problem Linkhttps://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1621

Solution Ideahttp://pavelsimo.blogspot.com/2012/06/uva-10680-lcm.html

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[1000002];

vector<ll int>prime;

void sieve()
{
    ll int n=1000000;
    ll int sq=sqrt(n);

    for(ll int i=4; i<=n; i=i+2) status[i]=true;

    prime.push_back(2);

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

ll int fact[1000005];

int main()
{
    ll int n,val,sq,q,rs,cnt,ans;
    sieve();
    while(scanf("%lld",&n) and n)
    {
        memset(fact,0,sizeof(fact));

        fact[1]=1;
        ans=1;
        for(ll int j=0; j<prime.size() and prime[j]<=n; j++)
        {
            val=prime[j];

            while(val<=n)
            {
                val=val*prime[j];

            }
            val=val/prime[j];
            fact[prime[j]]=val;

        }

        ll int cc=fact[5];
        cnt=0;
        while(fact[5]>1)
        {
            fact[5]=fact[5]/5;
            cnt++;
        }
        for(ll int k=cnt; k>0; k--)
        {
            fact[2]=fact[2]/2;
        }
        for(int i=1; i<=1000000; i++)
        {
            if(fact[i]!=0) ans=((ans%10)*(fact[i]%10))%10;
        }
        printf("%lld\n",ans);
    }

}

11388 - GCD LCM

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2383

Solution Ideahttp://blog.forthright48.com/2015/08/uva-11388-gcd-lcm.html

Solution :


#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll int ca,g,l,a,b;
    scanf("%lld",&ca);

    while(ca--)
    {
        scanf("%lld%lld",&g,&l);

        if(l%g!=0)
        {
            printf("-1\n");

        }
        else
        {
            a=g;
            b=l;
            printf("%lld %lld\n",a,b);
        }
    }
}


Thursday, June 30, 2016

1138 - Trailing Zeroes (III)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1138

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

1138 - Trailing Zeroes (III)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1138

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

Wednesday, June 29, 2016

1090 - Trailing Zeroes (II)

Problem Link :

Solution Idea : Interesting one. we have to find the number of 2's and number of 5's in (nCr*p^q). the ans is min(total number of 2's,total number of 5's).

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int fcnt(ll int n,ll int m)
{
    ll int cnt=0;

    while(n>0 and !(n%m))
    {
        n=n/m;
        cnt++;
    }
    return cnt;
}

int main()
{
    ll int t,n,r,p,q,a1,a2,a3,b1,b2,cnt,b3;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld%lld%lld",&n,&r,&p,&q);
        cnt=0;
        a1=fact(n,2);
        b1=fact(n,5);
        a2=fact(r,2);
        b2=fact(r,5);
        a3=fact(n-r,2);
        b3=fact(n-r,5);
        a1=a1-(a2+a3);
        b1=b1-(b2+b3);


        a2=fcnt(p,2)*q;
        b2=fcnt(p,5)*q;

        a3=a1+a2;
        b3=b1+b2;

        a1=min(a3,b3);

        printf("Case %lld: %lld\n",ca,a1);

    }

}


1028 - Trailing Zeroes (I)

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1028

Solution Idea : number of divisors

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool status[1000009];

vector<ll int>prime;

void sieve()
{
    ll int n=1000000;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4;i<=n;i=i+2) status[i]=1;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==0)
        {
                   for(int j=i*i;j<=n;j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3;i<=n;i=i+2)
    {
        if(status[i]==0)      prime.push_back(i);
    }
}

ll int nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int res=1;

    for(int i=0;i<prime.size() && prime[i]<=sq;i++)
    {
        int cnt=1;
  int c=prime[i];
        while(n%prime[i]==0)
        {
            n=n/prime[i];
            cnt++;
        }
        sq=sqrt(n);

        res= res*(cnt);
    }
    if(n!=1)
    {
        res=res*2;
    }
    return res;
}

int main()
{
    sieve();
   ll int t,n,ans;
   scanf("%lld",&t);

   for(ll int ca=1;ca<=t;ca++)
   {
       scanf("%lld",&n);
       ans=nod(n);
       ans--;
       printf("Case %lld: %lld\n",ca,ans);
   }

}

1067 - Combinations

Problem Linkhttp://lightoj.com/volume_showproblem.php?problem=1067

Solution Idea : ans is nCr. which is n!/r!(n-r)! .  as n and k is below <=10^6. so first we store the value of factorial 1 to 10^6 mod 1000003 in fact array.
then for finding n!/r!(n-r)! we need to find the modular inverse of r!(n-r)!. then ans is( n! * modular inverse of r!(n-r)!) mod 1000003.

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

ll int minv(ll int a,ll int m)
{
    ext_gcd(a,m);

    X=X%m;

    if(X<0) X=X+m;

    return X;
}


ll int fact[1000001];
ll int m=1000003;

int main()
{
    fact[0]=1;

    for(ll int i=1; i<=1000000; i++)
    {
        fact[i]=((fact[i-1]%m)*(i%m))%m;
    }

    ll int t,n,r,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&n,&r);

        ans= ((fact[r]%m)*(fact[n-r]%m))%m;
        ans=minv(ans,m);
        ans=(fact[n]*ans)%m;
        printf("Case %lld: %lld\n",ca,ans);
    }

}