অয়লার প্রাইম থেওরেম প্রবলেম

গোলবাচের ধারনা বা কঞ্জেকচার এবং অয়লারের থেওরেম।

গোলবাচের ধারনা বা গোলবাচের কঞ্জেকচার অনুযায়ী "২ এর চেয়ে বড় যে কোন সংখ্যাকে ৩ টা প্রাইম নাম্বারের যোগফল আকারে প্রকাশ করা যায় " তিনি ১ কে প্রাইম বা মৌলিক সংখ্যা হিসেবে চিন্তা করেছেন ।বিশ্বাস না হলে কাগজ কলম নিয়া একটু গুতা-গুতি করলেই বুঝতে পারবেন। আর আপনি চাইলে এই কঞ্জেকচারটাকে প্রমান করার চেষ্টাও করতে পারেন। যদি সফল হন তবে আপনাকে আর পায় কে? বিখ্যাত গনিতবিদ অয়লার এই কঞ্জেকচারকে আরও একটু বৃদ্ধি করে নতুন থেওরেম প্রমান করেন যা হল "৪ এর চেয়ে বড় বা সমান যে কোন জোড় সংখ্যাকে দুটি প্রাইম নাম্বারের যোগফল আকারে প্রকাশ করা যায়"। পরবর্তিতে তিনি নতুন থেওরেম প্রমান করেন যা হল "৭ এর চেয়ে বড় যে কোন সংখ্যা (জোড় বা বিজোড়) কে ৪ টা প্রাইম বা মৌলিক সংখ্যার যোগফল আকারে প্রকাশ করা যায়"।

উপরোক্ত তত্ত্বের ভিত্তিতে UVa 10168 প্রবলেমটা সেট করা হয়েছে। একবার ঠুস মেরে দেখতে পারেন। প্রবলেমটিতে ইনপুট সংখ্যাটি সর্বচ্চ্য 10^7 হতে পারে। সুতরাং সাধারণ ভাবে প্রাইম বের করার এখানে টেকনিক কাজ করবে না। এ জন্য আপনাকে সিভ মেথড শিখতে হবে। বাকি কাজটা একটু মাথা ঘামালেই পারবেন বলে আশা করি।

Problem Link: 10168 - Summation of Four Primes

N:B: Please don't copy the source code because it damages your brain.Try yourself first.Try to figure out the bug and critical test case.

Source Code in C++.

#include<bits/stdc++.h>
#define file freopen("in.txt","rt",stdin)
using namespace std;
int mark[10000009],prime[1000000],nprime =1;
int limit,n;
void PrimeNumber() /** Seive Method **/
{
    mark[1]=1;
    mark[0] =1;
    prime[nprime++]=2;

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

    for(int i=3; i<=n; i+=2)
    {
        if(!mark[i])
        {
            prime[nprime++]=i;

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }

}
int main()
{
    //file;
    n = 10000009;
    limit = sqrt(n+1);
    PrimeNumber();
    int n,d1,d2,x,y,z,w;
    while(scanf("%d",&n)==1)
    {
        if(n<=7)
        {
            printf("Impossible.\n");
            continue;
        }
        if(n%2==1)
        {
            d2 = n - 5;
            x = 2;
            y = 3;
            for(int i=1; prime[i]<=d2; i++)
            {
                int diff = d2 - prime[i];
                if(mark[diff]==0)
                {
                    z = prime[i];
                    w = diff;
                    break;
                }
            }
            printf("%d %d %d %d\n",x,y,z,w);
        }
        else
        {

            d1 = n/2;
            if(d1%2==1)
            {
                int k = n-4;
                x = 2;
                y =2;
                for(int i=1; prime[i]<=k; i++)
                {
                    int diff = k - prime[i];
                    if(mark[diff]==0)
                    {
                        z = prime[i];
                        w = diff;
                        break;
                    }
                }
                printf("%d %d %d %d\n",x,y,z,w);
            }
            else
            {
                for(int i=1; prime[i]<=d1; i++)
                {
                    int diff = d1 - prime[i];
                    if(mark[diff]==0)
                    {
                        printf("%d %d %d %d\n",prime[i],diff,prime[i],diff);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

Lightoj-1109 - False Ordering C++ Solution

Problem Link:1109 - False Ordering 

 NB: To solve this problem,You must have to know how to code NOD(number of divisor) in efficient way.

Implementation in C++:

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

vector<int>vt;
int divs[1009];
int NOD(int n)
{
    int cnt = 1;
    for(int i=2; i<=n; i++)
    {
        int c=0;
        while(n%i==0)
        {
            n/=i;
            c++;
        }
        if(c)
        {
            cnt=cnt*(c+1);
        }
    }
    return cnt;
}
int main()
{
    int test,num;
    scanf("%d",&test);
    for(int i=1; i<=1001; i++)
    {
        divs[i] = NOD(i);
    }
    for(int i=1; i<=35; i++)
    {
        for(int j=1000; j>=1; j--)
        {
            if(divs[j]==i)
                vt.push_back(j);
        }
    }
    for(int i=1; i<=test; i++)
    {
        scanf("%d",&num);
        printf("Case %d: ",i);
        cout<<vt[num-1]<<endl;
    }

    return 0;
}
 

UVa-579-Clock Hands

Problem link: Clock Hands

For detail information click hare 

Source code in C++:

#include<bits/stdc++.h>
#define file freopen("in.txt","rt",stdin)
int main()
{
   // file;
    int c=0,a;
    float h,m,H,d1,d2,ans;
    char str[10];
    while(gets(str))
    {
        a = strcmp(str,"0:00");
        if(a==0)
            break;
        if(strlen(str)==4)
        {
            h = str[0]-48;
            m = (str[2]-48)*10+(str[3]-48);

            H = h*60+m;
            d1 = H*0.5;
            d2 = m*6;
            ans= fabs(d1-d2);
            if(ans>180)
                ans-=360;
            printf("%.3f\n",fabs(ans));

        }
        else
        {
            h = (str[0]-48)*10+(str[1]-48);
            m = (str[3]-48)*10+(str[4]-48);

             H = h*60+m;
            d1 = H*0.5;
            d2 = m*6;
            ans= fabs(d1-d2);
            if(ans>180)
                ans-=360;
            printf("%.3f\n",fabs(ans));
        }
    }
    return 0;
}
 

Lightoj-1354 IP-Checking

Problem Link: IP Checking

NB: To understand the following code first learn about strtok() library function in C.Click Here

Source code in C:

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
    int test,i,sum=0,j=0,sum1,k,l;
    char str[50],str1[50];
    int a[5],b[5];
    char *temp, *temp1;
    int x,y;
    scanf("%d",&test);
    getchar();

    for(i=1; i<=test; i++)
    {
        gets(str);
        gets(str1);
        sum=0;
        k =0 ;
        temp = strtok(str, ".");
        while(temp!=NULL)
        {
            sum=0;
            for(j=0; j<strlen(temp); j++)
            {
                sum = sum*10 + (temp[j]-48);
            }
            a[k] = sum;
           // printf("%d ",a[k]);
            k++;
            temp = strtok(NULL, ".");
        }
        /*******************/
        k = 0;
        temp1 = strtok(str1, ".");
        while(temp1!=NULL)
        {
            sum=0;
            for(j=strlen(temp1)-1,l=0;j>=0;j--,l++)
            {
               sum = sum+(temp1[j]-48)* pow(2.00,(double)l);
            }

            b[k] = sum;
           // printf("%d ",a[k]);
            k++;
            temp1 = strtok(NULL, ".");
        }
        if(a[0]==b[0] && a[1]==b[1] && a[2]==b[2] && a[3]==b[3])
            printf("Case %d: Yes\n",i);
        else
           printf("Case %d: No\n",i);

    }
    return 0;
}

UVa-10189-Minesweeper Solution

Problem link: Minesweeper

Source Code in C++:

#include<bits/stdc++.h>
#define file freopen("in.txt","rt",stdin)
using namespace std;
char arr[110][110];
int ans[110][110];
int main()
{
    int n,m,c=0;
    char ch;
    // file;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        if(c!=0)
            cout<<endl;
        c++;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                cin>>ch;
                arr[i][j]=ch;
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                int cnt=0;
                if(arr[i][j]=='.')
                {
                    if(arr[i][j+1]=='*' && i>=1 && i<=n && j+1>=1 && j+1<=m)
                        cnt++;
                    if(arr[i-1][j+1]=='*'&& i-1>=1 && i-1<=n && j+1>=1 && j+1<=m)
                        cnt++;
                    if(arr[i-1][j]=='*'&& i-1>=1 && i-1<=n && j>=1 && j<=m)
                        cnt++;
                    if(arr[i-1][j-1]=='*'&& i-1>=1 && i-1<=n && j-1>=1 && j-1<=m)
                        cnt++;
                    if(arr[i][j-1]=='*'&& i>=1 && i<=n && j-1>=1 && j-1<=m)
                        cnt++;
                    if(arr[i+1][j-1]=='*'&& i+1>=1 && i+1<=n && j-1>=1 && j-1<=m)
                        cnt++;
                    if(arr[i+1][j]=='*'&& i+1>=1 && i+1<=n && j>=1 && j<=m)
                        cnt++;
                    if(arr[i+1][j+1]=='*'&& i+1>=1 && i+1<=n && j+1>=1 && j+1<=m)
                        cnt++;

                    ans[i][j]=cnt;
                }
            }

        }
        printf("Field #%d:\n",c);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(arr[i][j]=='*')
                {
                    printf("*");
                }
                else
                    cout<<ans[i][j];
            }

            cout<<endl;
        }
    }
    return 0;
}

UVa 10018: Reverse and Add

Problem Link:Reverse and Add

NB:There is trick to solve this problem thus read the problem carefully.You may get compile error in C for input format.So implement the program in .cpp extension.

Source code in C++:

#include<stdio.h>
#define lli long long int
#define file freopen("in.txt","rt",stdin)
int main()
{
    // file;
    lli num,revnum,sum1,sum2,d,r,cnt,num1;
    int test;
    while(scanf("%d",&test)!=EOF)
    {
        while(test--)
        {
            cnt=0;
            scanf("%lld",&num);
            do
            {
                num1 = num;
                sum1=0;
                while(num>0)
                {
                    r = num%10;
                    num = num/10;
                    sum1 = sum1*10+r;
                }
                num=num1+sum1;
                sum2=0;
                while(num>0)
                {
                    r = num%10;
                    num = num/10;
                    sum2 = sum2*10+r;
                }
                cnt++;
                num=sum1+num1;
            }
            while((num1+sum1)!=sum2);
            printf("%lld %lld\n",cnt,sum2);
        }
    }
    return 0;
}

 

The easiest DFS (depth first search) Problem: UVa 459

N:B First understand the core dfs algorithm and implement it in your own way.There are a lot of resources in online like GeeksForGeeks and in Wiki.


Problem Link: Graph Connectivity
For more practice : Go to here

Source code in C++:

#include<bits/stdc++.h>
#define lli long long int
#define file freopen("in.txt","rt",stdin)
using namespace std;
vector<int> node[101];
int vis[101];
void dfs(int n)
{
    for(int i=0; i<node[n].size(); i++)
    {
        if(vis[node[n][i]]==0)
        {
            vis[node[n][i]] = 1;
            dfs(node[n][i]);
        }
    }
}


int main()
{
    char str[3];
    int test,temp,sum=0;
    char f,s;
    cin>>test;
    scanf("\n");
    while(test--)
    {
        gets(str);
        sum=0;
        temp = str[0];
        memset(vis,0,sizeof vis);
        while(gets(str) and str[0])
        {

            node[str[0]].push_back(str[1]);
            node[str[1]].push_back(str[0]);
        }

        for(int i=65; i<=temp; i++)
        {
            if(vis[i]==0)
            {
                sum++;
                dfs(i);
            }
        }
        cout<<sum;
       if(test)
       {
           cout<<"\n\n";
       }
       else
        cout<<"\n";
       for(int i=65;i<=90;i++)
        node[i].clear();
    }
    return 0;
}