My solve Of Unline judge problems.

Solve of UVA 11716:Digital Fortress

Solve of UVA 11716:Digital Fortress

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int a,b,c,d,i,j,k,L;

    char z[10000],X;

    scanf("%d",&a);

    scanf("%c",&X);

    while(a--)

    {

        gets(z);

        b=strlen(z);

        c=sqrt(b);

        if((b-c*c)!=0)

        {

            cout<<"INVALID"<<endl;

            continue;

        }

        else

        {

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

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

                cout <<z[i];

        }

        cout<<endl;

    }

    return 0;

}

Solve of UVA 11723: Numbering Roads

Solve of UVA 11723: Numbering Roads

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long int a,b,c,e=1;

    double d;

    while(cin>>a>>b && a!=0 &&b!=0)

    {

        if(b>=a) cout<<"Case "<<e<<": "<<0<<endl;

        else if(a>b && (a-b)<=b*26) { d=a-b;cout<<"Case "<<e<<": "<<ceil((float)d/b)<<endl;}

        else cout<<"Case "<<e<<": "<<"impossible"<<endl;

        e++;

    }

    return 0;

}

Solve of UVA 11470: Square Sums

Solve of UVA 11470: Square Sums

#include<stdio.h>

int A[11][11];

int main()

{

    int n,i,j,k=1,a,b,sum;

    while(scanf("%d",&n)&&n)

    {

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

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

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

        printf("Case %d:",k++);

        for(a=0,b=n-1;a<=b;a++,b--)

        {

            if(a==b)

            {

                printf(" %d",A[a][b]);

                break;

            }

            sum = 0;

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

                sum += A[a][i] + A[i][a] + A[b][i] + A[i][b];

            sum -= A[a][a] + A[a][b] + A[b][a] + A[b][b];

            printf(" %d",sum);

        }

        printf("\n");

    }

    return 0;

}

Solve of UVA 11371: Number Theory for Newbies

Solve of UVA 11371: Number Theory for Newbies

#include<bits/stdc++.h>

using namespace std;

bool cmp(int a,int b)

{

    return a>b;

}

int main()

{

    long int n,i,j,k;

    while(scanf("%ld",&n)==1)

    {

        vector<int>v;

        k=n;

        while(k)

        {

            v.push_back(k%10);

            k/=10;

        }

        sort(v.begin(),v.end(),cmp);

        k=0;

        for(i=0;i<v.size();i++)

        {

            k=k*10+v[i];

        }

        sort(v.begin(),v.end());

        n=0;

        for(i=0;i<v.size();i++)

        {

            if(v[i]!=0)

            {

                n=v[i];

                j=i;

                for(i=0;i<v.size();i++)

                {

                    if(j!=i)

                    {

                        n=n*10+v[i];

                    }

                }

            }

        }

        printf("%ld - %ld = %ld = 9 * %ld\n",k,n,k-n,(k-n)/9);

    }

    return 0;

}

Solve of UVA 11344: The Huge One

Solve of UVA 11344: The Huge One

#include<bits/stdc++.h>

using namespace std;

int vag(string s,int n)

{

    int r=0,l,i,sum;

    l=s.size();

    if(l==1 && s[0]=='0')

        return r;

    else

    {

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

        {

            sum=r*10+(s[i]-'0');

            r=sum%n;

        }

        return r;

    }

}

int main()

{

    int n,i,j,tst,k,l,arr[1000],sz;

    string x;

    cin>>tst;

    while(tst--)

    {

        cin>>x;

        cin>>sz;

        k=0;

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

        {

            cin>>arr[i];

            k+=vag(x,arr[i]);

        }

        if(k==0)

        {

            cout<<x<<" - Wonderful."<<endl;

        }

        else

        {

            cout<<x<<" - Simple."<<endl;

        }

    }

    return 0;

}

Solve of UVA 12602: Nice Licence Plates

Solve of UVA 12602: Nice Licence Plates

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long int a,b,c,d,e,f;

    char x[3]={'\0'},z;

    cin>>a;

    while(a--)

    {

        scanf("%3s-%lld",x,&b);

        c=(x[0]-65)*676 + (x[1]-65)*26 + (x[2]-65)*1;

        d=c-b;

        if(d<0) d*=-1;

        if(d<=100) cout<<"nice"<<endl;

        else cout<<"not nice"<<endl;

    }

    return 0;

}

Solve of UVA 12611: Beautiful Flag

Solve of UVA 12611: Beautiful Flag

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int a,b,c,i,leng,widt,x1,x2,y1,y2;

    cin>>a;

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

    {

        cin>>b;

        leng=b*5;

        x1=(b*9)/4;

        x2=leng-x1;

        y1=(3*leng)/10;

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

        cout<<-x1<<" "<<y1<<endl;

        cout<<x2<<" "<<y1<<endl;

        cout<<x2<<" "<<-y1<<endl;

        cout<<-x1<<" "<<-y1<<endl;

    }

    return 0;

}

Solve of UVA 12542: Prime Substring

Solve of UVA 12542: Prime Substring

#include<iostream>
#include<stdio.h>
using namespace std;
int mx = 100000;
int arr[100010]={0};
void civ()
{
    int i,j,n;
    arr[0]=arr[1]=1;
    for(i=2;i*i<=mx;i++)
    {
        if(arr[i]==0)
        {
            for(j=2*i;j<=mx;j+=i)
                arr[j]=1;
        }
    }
}
int main()
{
    civ();

    int i,j,k,l,n,m,st[260],mn;
    string x;

    while(getline(cin,x))
    {
        if(x[0]=='0' && x[1]=='\0')
            return 0;
        l=x.size();
        for(i=0;i<l;i++)
        {
            st[i]=x[i]-'0';
        }
        mn=-1;
        for(i=0;i<l;i++)
        {
            m=0;
            for(j=i;j<l;j++)
            {
                m=m*10+st[j];
                if(m>mx)
                   break;
                else if(arr[m]==0)
                   mn=max(mn,m);
                //cout<<m<<endl;
            }
        }
        cout<<mn<<endl;
    }
    return 0;
}

Solve of UVA 12541: Birthdates

Solve of UVA 12541: Birthdates

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct persn
{
    char name[20];
    int day,month,year;
};

bool cmp(persn a,persn b)
{
    if(a.year == b. year )
    {
        if(a.month == b. month )
            return a.day<b.day;
        else return a.month < b.month;
    }

    return a.year<b.year;
}

int main()
{
    persn pr[111];
    int n,i,j,k,l,d,m,y;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>pr[i].name>>pr[i].day>>pr[i].month>>pr[i].year;
    }
    sort(pr,pr+n,cmp);

    cout<<pr[n-1].name<<endl<<pr[0].name<<endl;
    return 0;

}

Solve of UVA 12503: Robot Instructions

Solve of UVA 12503: Robot Instructions

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int a[110],b,c,d,i,f,j;

    char z[100]={'\0'};

    cin >> b;

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

    {

        cin>>c;

        d=0;

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

        {

            cin>>z;

            if(strcmp(z,"LEFT")==0){

                a[j]=-1;

                d--;

                //cout << "YES";

            }

            else if(strcmp(z,"RIGHT")==0){

                a[j]=1;

                d++;

            }

            else if (cin >> z >> f)

            {

                d+=a[f-1];

                a[j]=a[f-1];

            }

        }

        cout<<d<<endl;

    }

    return 0;

}

Solve of UVA 12527: Different Digits

Solve of UVA 12527: Different Digits

#include<iostream>

#include<stdio.h>

using namespace std;

int arr[5005]={0};

int mx=5005;

int dil(int n)

{

    int a,i,j,ari[12]={0};

    while(n)

    {

        ari[n%10]++;

        if(ari[n%10] > 1)

            return 3;

        n/=10;

    }

    return 2;

}

void cid()

{

    int n,i,j,k;

    for(i=1;i<mx;i++)

    {

        if(dil(i)==2)

            arr[i]=1;

    }

}

int main()

{

    cid();

    int a,b,i,j,k;

    while(scanf("%d%d",&a,&b)==2)

    {

        k=0;

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

        {

            k+=arr[i];

        }

        cout<<k<<endl;

    }

    return 0;

}

Solve of UVA 12416: Excessive Space Remover

Solve of UVA 12416: Excessive Space Remover

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

int main()
{
    long long int a,b,c,i,d,e,max,l;
    string z;
    while(getline(cin,z,'\n')){



        l=z.size();
        b=0;
        max=0;
        c=0;
        for(i=0;i<l;i++)
        {
            if(z[i]==' '){
                b++;
            }
            if(z[i]!=' ')
            {
                c=b;
                b=0;
            }
            if(max<c){
                max=c;

        }
        }

    if(max>0)
    {d=0;

    while(max!=1)
    {
        max=max/2+max%2;

        d++;
    }
    printf("%d\n",d);
    }
    else printf("%d\n", 0);
}
    return 0;
}

Solve of UVA 12239: Bingo!

Solve of UVA 12239: Bingo!

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,b,i,j;
    while(cin>>n>>b)
    {
        if(n==0 && b==0) break;
        int x[91]={0};
        int y[91]={0};
        for(i=0;i<b;i++)
        {
            cin>>j;
            x[j]=1;
            y[j]=1;
        }

        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(i!=j && x[i]==1 && x[j]==1)
                {
                    y[abs(i-j)]=1;

                }
            }
        }
        int ch=2;
        for(i=0;i<=n;i++)
        {

            if(y[i]!=1)
            {

                ch=3;
                cout<<'N'<<endl;
                break;

            }
        }
        if(ch==2)
            cout<<'Y'<<endl;
    }
    return 0;
}

Solve of UVA 12897 : Decoding Baby Boos

Solve of UVA 12897: 

Decoding Baby Boos

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k,l,tst,m;
    char y[1000000],a,b,x[128];
    cin>>tst;
    while(tst--)
    {
        scanf("%s",&y);
        scanf("%d",&n);
        for(i=0;i<128;i++) x[i]=i;
        while(n--)
        {
            cin>>a>>b;
            for(i='A';i<='Z';i++)
            {
                if(x[i]==b) x[i]=a;
            }
        }
        for(i=0;y[i];i++)
        {
            printf("%c",x[y[i]]);
        }
        printf("\n");

    }
    return 0;
}

Solve of uva 12895: Armstrong Number

Solve of uva 12895: Armstrong Number

#include<bits/stdc++.h>
using namespace std;
long long int powera(long long int a,long long int b)
{
    long long int x=1,i;
    for(i=1;i<=b;i++)
    {
        x*=a;
    }
    return x;
}
int main()
{
   long long int number, sum = 0, temp, remainder,n,i,x;

    cin>>n;
    while(n--)
    {
   scanf("%lld",&number);

   temp = number;
   sum=0;
   x=0;

   while(temp!=0)
   {
       x++;
       temp/=10;
   }
   temp=number;
   while( temp != 0 )
   {
      remainder = temp%10;
      sum = sum + powera(remainder,x);
      temp = temp/10;
   }

   if ( number == sum )
      printf("Armstrong\n");
   else
      printf("Not Armstrong\n");
    }
   return 0;
}

Solve of UVA 12908: The book thief

Solve of UVA 12908: The book thief

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n,i,j,k,l,x;
    while(scanf("%ld",&x)==1)
    {
        if(x==0) return 0;
        n=(-1+sqrt(1+8*x))/2;
        if((n*(n+1))/2==x)
            printf("%ld %ld\n",n+1,n+1);

        else
        printf("%ld %ld\n",((n+1)*(n+2))/2-x,n+1);

    }
    return 0;
}

Solve of UVA 12854: Automated Checking Machine

Solve of UVA 12854: Automated Checking Machine

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,e,f,g,h,i,j,k,l;
    while(scanf("%1d%1d%1d%1d%1d%1d%1d%1d%1d%1d",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j)==10)
    {
        if(a!=f && b!=g && c!=h && d!=i && e!=j) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
    return 0;
}

Solve of UVA 12802: Gift From the Gods

Solve of UVA 12802: Gift From the Gods

#include<bits/stdc++.h>
using namespace std;
int prime[1000100]={0};
void pri()
{
    long int n,i,j,k;
    prime[0]=prime[1]=1;
    for(i=0;i<1000100;i++)
    {
        if(!prime[i])
        {
            for(j=2*i;j<1000100;j+=i)
                prime[j]=1;
        }

    }
    prime[1]=0;
}

bool pal(long int x)
{
    long int n,i,j,k=0;
    n=x;
    while(n)
    {
        i=n%10;
        k=k*10+i;
        n/=10;
    }
    if(x==k) return true;
    else return false;
}

int main()
{
    long int n,i,j,k,l;
    pri();
    while(scanf("%ld" , &n)==1)
    {
        if(pal(n)==true && prime[n]==0)
        {
            printf("%ld\n",2*n);
            return 0;
        }
        else printf("%ld\n",2*n);
    }
    return 0;

}

Solve of UVA 12750: Keep Rafa at Chelsea!

Solve of UVA 12750: Keep Rafa at Chelsea!

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int i,j,k,l,n,m,a,b,tst;
    char x[500];
    cin>>tst;
    for(i=1;i<=tst;i++)
    {
        cin>>n;
        for(j=0;j<n;j++)
            cin>>x[j];
        for(j=0;j<n;j++)
        {
            if(x[j]!='W' && x[j+1]!='W' && x[j+2]!='W')
            {
                b=j+3;
                break;
            }
      }
        if(b>n)
        {
            printf("Case %d: Yay! Mighty Rafa persists!\n",i);
        }
        else
            printf("Case %d: %d\n",i,b);
    }
    return 0;
}

Please do not copy paste the code. Understand it. If there's any problem make a comment. 
Thank you.

গ্রাফ থিওরি - পর্ব-২ ( অ্যাডজেসেন্সি ম্যাট্রিক্স )

ম্যাট্রিক্স এর সাথে আমরা মোটামুটি পরিচিত। নাহলেও সমস্যা না। ম্যাট্রিক্স হল ১টা 2D অ্যারে। যেমন A একটি ম্যাট্রিক্স। এখানে ,A = 

আমরা ইচ্ছা করলে আমাদের গ্রাফ এর পুরো কথা এই ১টা মাত্র ম্যাট্রিক্স এর সাহায্যে তুলে ধরতে পারি। আপাতত সেটা না করে আমরা যদি এটা শুধু মাথায় রাখি যে যদি A হতে B  তে যাওয়া যায় তাহলে আমরা বলবো 1 . আর তা না হলে বলবো 0.  আমরা গতদিন যে অ্যাডজাসেন্ট নোড দেখেছিলাম এটা আসলে সেটাই। মানে যদি  নোড A আর  নোড B অ্যাডজাসেন্ট নোড হয় তাহলে আমরা বলবো 1. আর তা না হলে 0.

যেমন আমি যদি ১টি  গ্রাফ দেখি -

এখানে, ম্যাট্রিক্সটা হবে এরকম।

ব্যাপারটা হল, নোড A হতে শুধু নোড B এবং C তে যাওয়া সম্ভব। তাই এই দুইটার মান হবে ১ । আর বাকিগুলা ০।

তেমনি নোড B হয়ে শুধু নোড F এ যাওয়া সম্ভব। তাই এর মান হবে ১।

এভাবে নোড C হতে নোড E তে যাওয়া সম্ভব। নোড D হতে নোড A এবং C তে যাওয়া সম্ভব। তাই এর মান হবে ১।

.................................................................................( এভাবেই ম্যাট্রিক্সটা আপাতত গঠন করা হল )

এখানে যদি তীর চিহ্ন না দেয়া থাকে তার মানে হল উভয় নোড থেকে যাওয়া আসা করা যায়।

যেমনঃ

এই গ্রাফ এর ক্ষেত্রে ম্যাট্রিক্স টা হবেঃ

কেন এরকম হল??
আসলে আমরা জানি যে A আর  B এই দুই নোড এর মধ্যের এজ এ তীর চিহ্ন না দেয়ার মানে হল A হতে B তে আসা যাবে। আবার  B হতে  A তেও আসা যাবে । সেজন্য উভয়ক্ষেত্রে এর মান 1 দিতে হইসে। এটাই হল ম্যাট্রিক্স এর শুরু। এবং এখান থেকেই সব সমস্যার সমাধান করতে হয়।

ধন্যবাদ ।

গ্রাফ থিওরি - পর্ব-১ ( সাধারণ আলোচনা)

আমাদের অনেকের ধারণা গ্রাফ থিওরি মানেই হল একগাদা হাবিজাবি চিত্র আর হাজার হাজার লাইন এর কোড। ব্যাপারটা আসলে সেটা না। এটা আসলে অনেক বিচিত্র ১টা ক্ষেত্র। যেমন আমরা আমাদের প্রতিদিনের অনেক কিছুই এই গ্রাফ থিওরি দিয়েই সমাধান করি। যেমন ধর তুমি যখন স্কুল থেকে বাসায় যাও, রিক্সাওয়ালা চাচা তোমাকে সব চেয়ে শর্টকাট পথ দিয়ে নিয়ে যেতে চায়। আর সেই রাস্তা যদি ভাঙ্গা থাকে বা অন্য কোন সমস্যা থাকে তাহলে তিনি অন্য যে পথটা সবচেয়ে শর্টকাট হয় সেটা বিবেচনায় আনেন। মজার ব্যাপার হল তিনি অজান্তেই গ্রাফ থিওরি ব্যাবহার করছেন। এটা গ্রাফ থিওরির অনেক ব্যাসিক ১টা কথা। অনেকে মনে করে যে আমরা স্কুল কলেজে যে গ্রাফ পেপার এ জ্যামিতি করেছি এটাই গ্রাফ থিওরি.......... কিন্তু প্রকৃত পক্ষে এর সাথে গ্রাফ থিওরির কোন সম্পর্ক নায়।

Graph - 1.1

ধরি এটা ১টা শহরের ম্যাপ। এখানে ৬টা শহর আছে। A,B,C,D,E,F

শহর B হতে শহর A তে আসা যায়। তেমনি C হতে  B, E হতে C এবং F হতে  C তে আসা যায়। বোঝা যাচ্ছে ম্যাপ এ তীর চিহ্ন দেখে। এখন কথা হল এর সাথে গ্রাফ এর কি সম্পর্ক !

ব্যাপারটা হল প্রতিটা শহর এর কেন্দ্র থেকে আসলে এটা ( দূরত্ব )  হিসাব করা হয়। গ্রাফ এর ভাষায় একে বলে নোড (Node) । আর এখানে যে রাস্তা দেখা যাচ্ছে সেটাকে বলা হয় এজ( Edge)।

তো এখানে মোট নোড আছে ৬টা। আর এজ আছে ৪টা। আসল ব্যাপারটা হল পজিশন আর রাস্তা।যেমন দাবা খেলায় ঘোড়া ( Knight ) থাকে। ( আমরা যেটাকে বলি যে  ঘোড়া আড়াই কোট যেতে পারে ) তাহলে ১টা দাবার ছকটা এমন হতে পারে -

Graph - 1.2

এখানে তাহলে তার নোড হবে  a-3,a-5,b-2,b-6,c-4,,d-2,d-6,e-3 এবং e-5 । আর এজ হবে c-4 থেকে বাকি এজগুলার সংযোগ।
আশা করি নোড আর এজ এই ২টা টার্ম ক্লিয়ার ।

Adjacent Node :

অ্যাডজাসেন্ট নোড হল যদি ২টা নোড এর মধ্যে সরাসরি সংযোগ থাকে। যেমন ১ম চিত্রে নোড B হতে নোড A তে সরাসরি সংযোগ আছে। তাই A কে বলা হবে নোড B এর অ্যাডজাসেন্ট নোড।

অনেকসময় গ্রাফ এ কোন তীর চিহ্ন দেয়া থাকবে না। এর মানে হল এটা উভমুখী। যেমন 

Graph - 1.3

এটার বদলে শুধু এরকমও থাকতে পারে

Graph - 1.4

একই কথা।

...................................................................................................................................................................

আবার ১ম চিত্রঃ
এখানে প্রতিটা এজ এর পাশে লেখা আছে যে সেই দূরত্বটা কত কিলোমিটার। আসলে এটাকে বলা হয় কস্ট/ওয়েট ( Cost/Weight) ।আমরা এটাকেই নিয়ে সাধারনত সব হিসাব করি। যেমন নোড B হতে নোড A এর Distance 10KM । এই ওয়েটের মান যদি দেয়া না থাকে তাহলে তার সাধারণ মান হয় ১।


এই পথ যদি না শেষ হয় .................

গ্রাফ থিওরিতে পথ কে পাথ( Path ) বলা হয় । যেমনঃ

Graph - 1.5

C হতে A তে যাওয়ার ২টা উপায় আছে।

1. Cহতে B তে যাওয়া এবং তারপর B হতে A তে যাওয়া।
2. সরাসরি C হতে A তে যাওয়া।

এখানে উভয়ই হল C হতে A তে যাওয়ার পাথ(Path) ।

শর্টেস্ট পাথঃ
কত কম ওয়েটে এক নোড হতে অপর নোড এ যাওয়া যায় =  শর্টেস্ট পাথ।
যেমন, এখানে ১ম উপায়ে ( Cহতে B তে যাওয়া এবং তারপর B হতে A তে যাওয়া ) মোট ওয়েট লাগে ১৮। আর ২য় উপায়ে (সরাসরি C হতে A তে যাওয়া ) সেটা লাগে ২১। সুতরাং তুমি নিশ্চয় ১ম পাথ ব্যাবহার করতে চাইবা। এটাই হল শর্টেস্ট পাথ।( এ ব্যাপার এ পরে আরো বিস্তারিত আলচনা করা হবে ) ।





আশা করি মোটামুটি বোঝাতে পারলাম। এখন কথা হল গ্রাফ থিওরি কেন দরকার? আমরা যে শুধু ট্রাফিক পলিশ দের মত রাস্তার হিসাব দেখবো তা না। আসলে অনেক সময় ডেটা কোন সোর্স থেকে কোন ডিভাইস এ যাবে এবং কোন পাথ ব্যাবহার করবে সেটা এই থিওরি ছাড়া সম্ভব হয় না। নেটওয়ার্কিং এর জন্য গ্রাফ থিওরি একদমই ফরজ। আর এগুলা ছাড়াও আরো অনেক কিছু আছে যা এই গ্রাফ থিওরির সাহায্যে সমাধান করতে হয়। আমরা প্রধানত কন্টেস্ট এর জন্য অনেক সমস্যার আলোচনা করবো পরবর্তী সব পোস্ট এ ।

ধন্যবাদ।