10041-Vito’s family-Solution hints

https://uva.onlinejudge.org/external/100/10041.pdf


This is a easy problem . Solving techniques is given below :

1 . In this problem it is said to determine the shortest distance of a given set of numbers as defined Vito's relatives house no . Vito wants to minimize the total distance .

2 . Minimizing the total distance or determining sum of minimal distance we need to sort the given set of input then need to find median because from median every relative's house distance is minimum distance .

3 . Now sum the subtraction of median and right sides numbers  using loop.  

4 . Again sum the subtraction of left sides  numbers and median .

5 . Here the total sum is the desired answer .


An accepted code is given below :


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

int main()
{
    long long int t,a,b,arr[1000]={0},sum;

    scanf("%lld",&t);

    while(t>0)
    {
        sum=0;

         scanf("%lld",&a);

         for(int i=0;i<a;i++)
         {
             scanf("%lld",&arr[i]);
         }

         sort(arr,arr+a);

         if(a%2!=0)
         {
             b=arr[a/2];
         }
         else
         {
             b=arr[a/2];
         }

         for(int i=a/2+1;i<a;i++)
         {
             sum=sum+abs(arr[i]-b);
         }

         for(int i=a/2-1;i>=0;i--)
         {
             sum=sum+abs(b-arr[i]);
         }

         printf("%lld\n",sum);

        t--;
    }

    return 0;

}

10192-Vacation-solution hints

https://uva.onlinejudge.org/external/101/10192.pdf

In first view you may think that it is hard one but not like that it's easy and if you know the LCS(Longest Common subsequence) then you can easily solve the problem . it's nothing but to find the common subsequence between two strings . For details of LCS algorithm please visit the links below : 

https://www.youtube.com/watch?v=NnD96abizww

http://www.thecrazyprogrammer.com/2015/05/c-program-for-longest-common-subsequence-problem.html

N.B : please be careful for using array because it may become the main  reason of getting Runtime error . 

An accepted code is given below : 

#include<bits/stdc++.h>

using namespace std;

int c[501][501];

int max1(int x , int y)

{

    if(x>y)

    {

        return x;

    }

    else

    {

        return y;

    }

}

int lcs(string x , string y)

{

    int m,n;

    m=x.length();

    n=y.length();

    for(int i=0;i<=x.length();i++)

    {

        c[i][0]=0;

    }

    for(int j=0;j<=y.length();j++)

    {

        c[0][j]=0;

    }

    for(int i=1;i<=x.length();i++)

    {

        for(int j=1;j<=y.length();j++)

        {

            if(x[i-1]==y[j-1])

            {

                c[i][j]=c[i-1][j-1]+1;

            }

            else

            {

                c[i][j]=max1(c[i-1][j],c[i][j-1]);

            }

        }

    }

    return c[m][n];

}

int main()

{

    string x,y;

    int i=1;

    while(getline(cin,x) && x!="#")

    {

        getline(cin,y);

    cout<<"Case #"<<i<<": you can visit at most "<<lcs(x,y)<<" cities."<<endl;

    i++;

    }

    return 0;

}

(Happy coding)

 

488-Triangle wave-UVA solution hints

https://uva.onlinejudge.org/external/4/488.pdf

Here it's an easy problem but there's only one trick that is "There is a blank line after each separate waveform, excluding the last one" . It's means you have to print a blank line after every waveform except the last one so in last line when programme will terminate there no blank line is needed . 

1 . As it is said in the sample input that  3 is the amplitude which means how high the horizontal line will be and frequency is 2 that means how times same triangle should be print . 

2 . It is also said that Amplitude will never been greater than 9 so you can store 1,22,333,4444,55555 just like this until 9 into an string array and print those how many times it's needed to print. 

N.B : I have got 10 times presentation error for problem of printing blank line so handle it carefully . 

An accepted code is given below : 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    string wave[100]={"1","22","333","4444","55555","666666","7777777","88888888","999999999"};

    int i,t,j,a,b;

    scanf("%d",&t);

    while(t--)

    {

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

        while(b--)

        {

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

            {

                cout<<wave[j]<<endl;

            }

            for(j=a-2;j>=0;j--)

            {

                cout<<wave[j]<<endl;

            }

            if(b || t)

            {

            printf("\n");

            }

        }

    }

    return 0;

}

    

12626 - I ❤ Pizza - Solution hints

https://uva.onlinejudge.org/external/126/12626.pdf

This is an easy string processing problem . just think for sometimes regarding the problem and i guess you will find a way to solve it but if you don't then don't worry i'm here for giving you logic hints for solving this problem . ok let's start : 

1 . Here it is said that you have to determine how many MARGARITA pizza you can get from a given string . So 1st of all you need to know how many words in "MARGARITA" word without repetition .

2 .  Here M 1 time , A 3 times , R 2 times , G 1 time, I 1 time , T 1 time . store the word "MARGIT" into a string and store the corresponding letter frequency "1,3,2,1,1,1" into a integer array . 

3 . Now check how many times the character "M,A,R,G,I,T" exists in given string . Then just divide the new frequency by the old for corresponding letter and again store in a new integer array . 

4 . Now just sort the new array and print the 1st element as the after dividing the frequency the minimum result will be the answer because all the other elements frequency can satisfy the minimum resultant one . 

An accepted code is given below : 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    string p="MARGTI";

    string line;

    int arr[10]={1,3,2,1,1,1};

    int t,i,j,s,d,k;

    scanf("%d",&t);

    while(t>0)

    {

        int arr1[1000]={};

        s=0;

        cin>>line;

        for(i=0;i<p.length();i++)

        {

            d=0;

            for(j=0;j<line.length();j++)

            {

                if(p[i]==line[j])

                {

                    d++;

                }

            }

            arr1[s++]=d/(arr[i]);

        }

        sort(arr1,arr1+s);

        printf("%d\n",arr1[0]);

        t--;

    }

    return 0;

}

834-Continued Fraction-solution hints

https://uva.onlinejudge.org/external/8/834.pdf

This problem seems to be hard but not hard at all . It's a mathematical problem . You can easily implement this code if you know clearly about Using Euclid's GCD algorithm to make a continued fraction . Please go through the following link to know details about Euclid's GCD algorithm :

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#section3

solution steps :

1 . Take two input as N & D which indicate nominator and denominator.

2 . Now divide the N by D and put it to an array .

3 . Now mode N by D to get the remaining part also assign D to N and the remaining part to D .

4 . go back to step 2 until the remaining part becomes 0 .

Note : Once again try to get Euclid's algorithm clearly otherwise you can't get the r8 path to solve this problem .

An accepted code is given below :

~1st try yourself if you can't then just take idea never copy paste code~

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

int main()
{
    long long int N,D,s,m,i,j;

    while(scanf("%lld%lld",&N,&D)==2)
    {
        i=0;
        m=1;
        long long int arr[q]={0};

        while(m!=0)
        {

        s=N/D;
        m=N%D;

        arr[i++]=s;

        N=D;
        D=m;
        }

        printf("[%lld;",arr[0]);

        for(j=1;j<i;j++)
        {
            if(j==(i-1))
            {
                printf("%lld]\n",arr[j]);
            }
            else
            {
            printf("%lld,",arr[j]);
            }
        }

    }

    return 0;

}
  

10107-What is the Median?-solution hints

https://uva.onlinejudge.org/external/101/10107.pdf

In first look the problems seems to be easy but someone will get confused seeing the sample input output but don't worry it's after all an easy problem . the problem statement says that ,

1 . you have to determine current median that means you have to determine the median dynamically for every input .

2 . median value is that which divides an array into two equal parts and it differs for even number and odd number so you have to think what you should do when determining even numbers median and when odd numbers median .

3. You can use build in Sort function or Insertion sort Algorithm here to sort the value then calculate the median .

4 . Just give two if else statement which indicates when even and when odd . that's it .

An accepted code for this problem is given below :


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

int main()
{
    long long int i=1,j,k,s;
    long long int arr[m]={0};


    while(scanf("%lld",&arr[i])==1)
    {
        sort(arr,arr+(i+1));

        if(i==1)
        {
             printf("%lld\n",arr[i]);
        }
        else if(i%2==0)
        {
            s=(arr[i/2]+arr[i/2+1])/2;
            printf("%lld\n",s);
        }
        else if(i%2!=0)
        {
            s=arr[i/2+1];
            printf("%lld\n",s);

        }

        i++;
    }

    return 0;
}

12114 - Bachelor Arithmetic-Solution hints

https://uva.onlinejudge.org/external/121/12114.pdf


This is a adhoc problem . The hints for solving this problem is given below :

1 . Here in this problem the probability for bachelor marriages increasing is not possible as the smaller value is -1 .

2 .  If B is equal to 1 or 0 then it also can not be determined .

3 . Otherwise when B>=S then the probability for a bachelor remains same because the because when B>S then the bachelor's number get finished but spinster remains so there'e no scope of increasing or decreasing bachelor's marriage probability .

4 . when B<S then the probability decreases as the number of spinster is less than the number of bachelor which is really hard to get all the bachelor married so the bachelor number remains which decreases bachelor's marriage probability .

A sample accepted solution is given below :


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

int main()
{
    int B,S,i=1;

    while(scanf("%d%d",&B,&S)==2)
    {
        if(B==0 && S==0)
        {
            break;
        }
        else if(B==0 || B==1)
        {
            printf("Case %d: :-\\\n",i);
        }
        else if(B<=S)
        {
            printf("Case %d: :-|\n",i);
        }
        else if(B>S)
        {
            printf("Case %d: :-(\n",i);
        }

        i++;
    }

    return 0;
}