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

How to represent an odd number sum of any three prime numbers.

Codeforces Number Theory Problem: D - Dima and Lisa 

Tutorial:

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10⁹ maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in O(sqrt(n) complexity). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

Source Code in C++:

#include<bits/stdc++.h>
using namespace std;
int mark[1000000],PrimeNumber[1000000];
int n = 1000,nprime,limit;
void PrimeNum()
{
    mark[1]=1;

    PrimeNumber[nprime++]=2;

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

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

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }
}
int main()
{
    limit = sqrt(n+1);
    PrimeNum();
    int a,b;
    bool ok=false;
    cin>>a;
    int prime;
    for(int i=a-1;; i--)
    {
        ok =true;
        for(int j=2; j*j<=i; j++)
        {
            if(i%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            prime=i;
            break;
        }
    }
    int need = a - prime,got;


    for(int i=0;; i++)
    {

        got = need - PrimeNumber[i];

        ok =true;
        for(int j=2; j*j<=got; j++)
        {
            if(got%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            b=PrimeNumber[i];
            break;
        }

    }
    if(a==3)
    {
        cout<<1<<"\n"<<3<<endl;
    }
    else if(got==0)
    {
        printf("2\n");
        cout<<prime<<" "<<b<<endl;
    }
    else
    {
        printf("3\n");
        cout<<prime<< " "<<got<< " "<<b<<endl;
    }

    return 0;
}

Easy topological sort problem in C++. UVa-10305

Please don't copy code.At first try to understand the topological sort algorithm.
Best explanation in Bangla Language টপোলজিকাল সর্ট.


Implementation in C++.

Source code:

#include<bits/stdc++.h>
using namespace std;
int result[101];
vector<int>ans;
int main()
{
    vector<int>G[101];

    int n,m;
    while(cin>>n>>m)
    {
        if(n==0 && m==0)
            break;
        ans.clear();
        memset(result,0,sizeof result);
        for(int i=0; i<m; i++)
        {
            int node1,node2;
            cin>>node1>>node2;
            G[node1].push_back(node2);
            result[node2]++;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(result[j]==0)
                {
                    for(int k=0; k<G[j].size(); k++)
                    {
                        int t = G[j][k];
                        result[t]--;
                    }
                    result[j]=-1;
                    ans.push_back(j);
                    break;
                }
            }

        }
        for(int i=0; i<n; i++)
        {
            cout<<ans[i];
            if(i!=n-1)
                cout<<" ";
        }
        cout<<endl;

        for(int i=0;i<=n;i++)
        {
            G[i].clear();
        }

    }
    return 0;
}