1111 - Best Picnic Ever

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

Solution :

#include<bits/stdc++.h>

using namespace std;
vector<int>v[1002];
vector<int>vv;
int visited[1002];

int arr[1002];

void bfs(int s)
{
    queue<int>q;
    memset(visited,-1,sizeof(visited));
    visited[s]=0;
    arr[s]=arr[s]+1;
    q.push(s);

    int u,p,x;

    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];
            if(visited[p]==-1)
            {
                visited[p]=visited[u]+1;
                x=arr[p]=arr[p]+1;
                q.push(p);

            }
        }

    }
    //w= visited[d]-visited[s];
    //return w;
}

int main()
{
    int t,n,m,k,a,b;

    scanf("%d",&t);

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

        for(int i=1; i<=k; i++)
        {
            scanf("%d",&a);
            vv.push_back(a);
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
        }
        for(int i=0; i<k; i++)
        {
            bfs(vv[i]);

        }
        for(int i=0; i<1002; i++) v[i].clear();
        int cnt=0;

        for(int i=1; i<=n; i++ )
        {
            if(arr[i]==k) cnt++;
        }

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

        vv.clear();
        memset(arr,0,sizeof(arr));
    }

}

1093 - Ghajini

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

Solution :

#include<bits/stdc++.h>

#define mix 100002

using namespace std;


int arr[mix];

struct Node
{
    int mn;
    int mx;
}  tree[mix*4];



void init(int node, int b,int e)
{

    if(b==e)
    {
        tree[node].mn=arr[b];
        tree[node].mx=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node].mn=min(tree[left].mn,tree[right].mn);
    tree[node].mx=max(tree[left].mx,tree[right].mx);

}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.mn=1000000000;
        temp.mx=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);


    Node p3;
    p3.mx=max(p1.mx,p2.mx);
    p3.mn=min(p1.mn,p2.mn);

    return p3;
}




int main()
{


    int t,n,d;
    Node temp;
    int ans;

    scanf("%d",&t);

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

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

        init(1,1,n);

        ans=0;

        for(int i=1;i+d-1<=n;i++)
        {
           temp=query(1,1,n,i,i+d-1);
           ans=max(ans,temp.mx-temp.mn);

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

1083 - Histogram

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];

struct Node
{
    int val;
    int index;
}  tree[mx*4];

vector<int>v;

void init(int node, int b,int e)
{
    int c,d;

    if(b==e)
    {
        c=tree[node].val=arr[b];
        d=tree[node].index=b;
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);


    if(tree[left].val<tree[right].val)
    {
        c=tree[node].val=tree[left].val;
        d=tree[node].index=tree[left].index;
    }
    else
    {
        c=tree[node].val=tree[right].val;
        d=tree[node].index=tree[right].index;
    }


}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.val=9000000;
        temp.index=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);

    if(p1.val<p2.val) return p1;
    else return p2;
}




int main()
{


    int t,n,q,l,r,ans,mn,L,R;
    scanf("%d",&t);
    Node temp;
    for(int ca=1; ca<=t; ca++)
    {


        scanf("%d",&n);

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


        init(1,1,n);

        temp=query(1,1,n,1,n);
        ans=temp.val;
        mn=ans;
        ans=n*ans;

        int mid=temp.index;

        l=1;
        r=mid-1;
        L=mid+1;
        R=n;

        if(l<=r)
        {
            v.push_back(l);
            v.push_back(r);
        }
        if(L<=R)
        {
            v.push_back(L);
            v.push_back(R);
        }


        while(v.size())
        {

            temp=query(1,1,n,v[0],v[1]);
            mn=(v[1]-v[0]+1)*temp.val;
            ans=max(mn,ans);
            mid=temp.index;
            l=v[0];
            r=mid-1;
            L=mid+1;
            R=v[1];

            if(l<=r)
            {
                v.push_back(l);
                v.push_back(r);
            }
            if(L<=R)
            {
                v.push_back(L);
                v.push_back(R);
            }

            v.erase(v.begin()+0);
            v.erase(v.begin()+0);
        }




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

    }

}

1112 - Curious Robin Hood

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];
int global;

void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=(tree[left]+tree[right]);


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return p1+p2;
}

void update(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=val;
        return ;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

void update1(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=global+val;
        return ;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update1(left,b,mid,i,val);
    update1(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}



int main()
{

    int t,n,q,l,r,ans,v;
    scanf("%d",&t);

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


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

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


       init(1,1,n);



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

       for(int i=1;i<=q;i++)
       {
           scanf("%d",&l);

           if(l==1)
           {
               scanf("%d",&r);
               update(1,1,n,r+1,0);
                printf("%d\n",global);
           }
           else if(l==2)
           {
               scanf("%d%d",&r,&v);

               update1(1,1,n,r+1,v);

           }
           else if(l==3)
           {
               scanf("%d%d",&r,&v);
               ans=query(1,1,n,r+1,v+1);
           printf("%d\n",ans);

           }


       }


   }

}

1082 - Array Queries

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];


void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=min(tree[left],tree[right]);


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return mx;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return min(p1,p2);
}



int main()
{

    int t,n,q,l,r,ans;
    scanf("%d",&t);

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


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

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


       init(1,1,n);



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

       for(int i=1;i<=q;i++)
       {
           scanf("%d%d",&l,&r);
           ans=query(1,1,n,l,r);
           printf("%d\n",ans);
       }


   }

}

1033 - Generating Palindromes

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

Solution :

#include<bits/stdc++.h>

using namespace std;

int a[102][102];

int main()
{
    string text,pattern;

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

    for(int ca=1; ca<=t; ca++)
    {
        cin>>text;
        pattern=text;
        reverse(pattern.begin(),pattern.end());

        l1=text.size();

        memset(a,0,sizeof(a));

        for(int i=1; i<=l1; i++)
        {
            for(int j=1; j<=l1; j++)
            {
                if(text[i-1]==pattern[j-1]) a[i][j]=a[i-1][j-1]+1;
                else a[i][j]=max(a[i-1][j],a[i][j-1]);
            }
        }

        cout<<"Case "<<ca<<": "<<l1-a[l1][l1]<<endl;

    }



}

1043 - Triangle Partitioning

Problem Link : http://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 Link : http://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);
        }

    }

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();

    }

}

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

1141 - Number Transformation

Problem Link : http://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 Link : http://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);
    }

}

1311 - Unlucky Bird

Problem Link : http://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);

    }

}

1337 - The Crystal Maze

Problem Link : http://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();

    }

}

1020 - A Childhood Game

Problem Link : http://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);
    }


}