UVA 484 - The Department of Redundancy Department Solution

problem link-click here

This problem can't be solved without using STL MAP. the general rule or using array may  result in TLE. so learn map for solving this problem. for map go to the link below:

C++ Tutorial for Beginners 45 - C++ Map

an accepted code is as follows:

#include<iostream>
#include<map>
#include<vector>
using namespace std;

vector<int> v;
map<int,int> m;

int main()
{
    int n;

    while(cin>>n)
    {
        if(m[n]==0)
        {
            v.push_back(n);
            m[n]=1;
        }
        else
        {
        m[n]=m[n]+1;
        }
    }

    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" "<<m[v[i]]<<endl;
    }

    return 0;
}

Uva 673 - Parentheses Balance Solution

Problem link-click here

This problem can't be solved without using the stack. there's a built-in library function of stack in C++. try google for the syntax of stack library or see the below code to understand the use of stack.

an accepted code is as follows:

#include<iostream>
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;

int main()
{
    int t;

    scanf("%d",&t);
    cin.ignore();

    while(t--)
    {
        string str;

        getline(cin,str);

        stack<char> stk;

        for(int i=0;i<str.length();i++)
        {
            if(!stk.empty() && str[i]==')' && stk.top()=='(')
            {
                stk.pop();
            }
            else if(!stk.empty() && str[i]==']' && stk.top()=='[')
            {
               stk.pop();
            }
            else
            {
                stk.push(str[i]);
            }
        }

        if(stk.empty())
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }

    return 0;
}

UVA 1583 - Digit Generator Solution

Problem link-Click here

it's an easy implement based problem.just follow the statement carefully. you need to process 100 number back to the given number to get desired result. for example if n=2005 then you have to check 2005-100=1905 to 2004 to get the generator of 2005. there's a constraint and which is if n is less than 100 then you have to go to n/2 to n-1 to get the generator and if can't be found just print 0.

an accepted code is as follows:

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

int process(int n)
{
    int sum=n;

    while(n!=0)
    {
        sum=sum+(n%10);
        n=n/10;
    }
    return sum;
}

int main()
{
    int t,n;

    scanf("%d",&t);
    while(t--)
    {
        bool flag=0;
        int s;

        scanf("%d",&n);

        if(n>100)
        {
            for(int i=n-100;i<n;i++)
            {
                if(process(i)==n)
                {
                    flag=1;
                    s=i;
                    break;
                }
            }
        }
        else
        {
            for(int i=n/2;i<n;i++)
            {
                if(process(i)==n)
                {
                    flag=1;
                    s=i;
                    break;
                }
            }
        }

        if(flag==1)
        {
            printf("%d\n",s);
        }
        else
        {
            printf("%d\n",0);
        }
    }
    return 0;
}

UVA 490 - Rotating Sentences Solution

Problem link-Click here

in this problem i faced the problem of when to stop taking input but after a while i realize that i have to take input until end of file and also have to stop taking input pressing Ctrl+z button. so do that.

an accepted code is as follows:

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

int main()
{
    string str[105];

    int p=0,best_len=0;

    while(getline(cin,str[p]))
    {
        if(str[p].length()>best_len)
        {
            best_len = str[p].length();
        }
        p++;
    }

    for(int i=0;i<best_len;i++)
    {
        for(int j=p-1;j>=0;j--)
        {
            if(str[j].length()>i)
            {
                cout<<str[j][i];
            }
            else
            {
                cout<<" ";
            }
        }
        cout<<endl;
    }
}

UVA 11716 - Digital Fortress Solution

Problem link-Click here

One of the string processing problem. try to figure out the pattern behind this problem.

accepted code is as follows:


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

int main()
{
    int t;
    cin>>t;
    cin.ignore();

    while(t--)
    {
        string str;

        getline(cin,str);

        double m=sqrt(str.length());
        int m1=sqrt(str.length());

        if(m==m1)
        {
            for(int i=0;i<m1;i++)
            {
                for(int j=i;j<str.length();j=j+m1)
                {
                    cout<<str[j];
                }
            }
            cout<<endl;
        }
        else
        {
            cout<<"INVALID"<<endl;
        }

    }

    return 0;
}

UVA 10200 - Prime Time solution

problem link-click here

Solving this problem i have learnt a new technique which is how to reduce time complexity and make it o(1) from o(n^3) that means i get output at constant time. i have used cumulative sum to solve this problem. now obviously you must be curious to know what actually cumulative sum is. try google for getting cumulative sum.

an accepted code is as follows:

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

vector<int> v;
bool arr[s];

void sieve()
{
    v.push_back(2);

    for(int i=3;i<=s;i+=2)
    {
        if(arr[i]==0)
        {
            v.push_back(i);

            for(int j=3;i*j<=s;j+=2)
            {
                arr[i*j]=1;
            }
        }
    }
}

int prime(long long int n)
{
    int i=0;

    while(v[i]*v[i]<=n)
    {
        if(n%v[i]==0)
        {
            return 0;
        }

        i++;
    }

    return 1;
}

int main()
{
    sieve();

    vector<double> v1;
    long long int n;

    for(int i=0;i<=10001;i++)
    {
        n=i*i+i+41;
        v1.push_back(prime(n));

        if(i>0)
        {
          v1[i]=v1[i]+v1[i-1];
        }
    }

    int a,b;
    double e;

    while(scanf("%d%d",&a,&b)==2)
    {
        if(a==0)
        {
            printf("%.2lf\n",((v1[b]-0)/(abs(b-a)+1))*100)+1e-8;
        }
        else
        {
          e=((v1[b]-v1[a-1])/(abs(b-a)+1))*100+1e-8;
          printf("%.2lf\n",e);
        }
    }

    return 0;
}

UVA 10222 - Decode the Mad man Solution

10222 - Decode the Mad man

it's a string related easy problem.

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

int main()
{
int i,l;
string str;
while(getline(cin,str))
{

l=str.length();

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

    switch(str[i])
        {
        case ' ':    printf(" "); break;
        case 'a':
        case 'A':     printf("["); break;
        case 's':
        case 'S':     printf("]"); break;
        case 'z':
        case 'Z':     printf("'"); break;
        case 'x':
        case 'X':     printf("\\"); break;
        case 'e':
        case 'E':     printf("q"); break;
        case 'r':
        case 'R':     printf("w"); break;
        case 't':
        case 'T':     printf("e"); break;
        case 'y':
        case 'Y':     printf("r"); break;
        case 'u':
        case 'U':     printf("t"); break;
        case 'i':
        case 'I':     printf("y"); break;
        case 'o':
        case 'O':     printf("u"); break;
        case 'p':
        case 'P':     printf("i"); break;
        case '[':     printf("o"); break;
        case ']':     printf("p"); break;
        case 'd':
        case 'D':     printf("a"); break;
        case 'f':
        case 'F':     printf("s"); break;
        case 'g':
        case 'G':     printf("d"); break;
        case 'h':
        case 'H':     printf("f"); break;
        case 'j':
        case 'J':     printf("g"); break;
        case 'k':
        case 'K':     printf("h"); break;
        case 'l':
        case 'L':     printf("j"); break;
        case ';':     printf("k"); break;
        case '\\':      printf(";"); break;
        case 'c':
        case 'C':     printf("z"); break;
        case 'v':
        case 'V':     printf("x"); break;
        case 'b':
        case 'B':     printf("c"); break;
        case 'n':
        case 'N':     printf("v"); break;
        case 'm':
        case 'M':     printf("b"); break;
        case ',':     printf("n"); break;
        case '.':     printf("m"); break;
        case '/':     printf(","); break;
        case 'q':
        case 'Q':
        case 'w':
        case 'W':
        case '{':
        case '}':
        case ':':
        case '"':
        case '|':
        case '<':
        case '>':
        case '?':    break;
        default :
        printf("l");
        break;
        }

}
printf("\n");
}
return 0;
}

UVA 11152 - Colourful Flowers Solution

Problem link-click here

it's an easy geometrical problem. there's some formula's to cope with this problem. see the codes to get better.

#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;

int main()
{
    double a,b,c;

    while(cin>>a>>b>>c)
    {
       double s = (a+b+c)/2;

       double p= abs( sqrt((s-a)*(s-b)*(s-c)/s) );

       double r= pi*p*p;

       double q= sqrt(s*(s-a)*(s-b)*(s-c));

       double t= abs(q-r);

       double r1= (a*b*c)/(4*q);

       double u= pi * r1 * r1;

       double v= u-q;

       cout<<fixed<<setprecision(4)<<v<<" "<<t<<" "<<r<<endl;
    }
    return 0;
}

UVA 11044 - Searching for Nessy Solution

problem link-click here

in this problem, you have to divide both the rows and columns by 3 and have to multiply them as every sonar control 3x3 matrix according to the problem statement.

An accepted code is as follows:

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

int main()
{
    int n,m,t;

    cin>>t;

    while(t--)
    {
        cin>>n>>m;

        cout<<(n/3)*(m/3)<<endl;
    }

    return 0;
}

A program to check whether a number is prime or not

#include <stdio.h>
#include<math.h>


int main()
{
int number, counter, isprime = 0;

printf("please enter the positive integer value to identified prime or composite\n");

scanf("%d",&number);

for(counter=2; counter <= sqrt(number); counter++)
{

if((number % counter)==0){

isprime=1;

}

}
if(isprime==0){

printf("%d is a prime number",number);
}else{

printf("%d is a composite number",number);
}

return 0;

}

UVA 10533 - Digit Primes solution

problem link-click here

here i have used an interesting tool which is cumulative sum to get rid from TLE. see the code for better understand. try google for cumulative sum.

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

bool arr[m];
int arr1[m];

void sieve()
{

    for(int i=2;i<=m;i++)
    {
        if(arr[i]==0)
        {
            int n=i,sum=0;

            while(n!=0)
            {
                sum=sum+(n%10);
                n=n/10;
            }

            if(arr[sum]==0)
            {
                arr1[i]=1;
            }

            for(int j=2;i*j<=m;j++)
            {
                arr[i*j]=1;
            }
        }
    }

    for(int i=1;i<=m;i++)
    {
        arr1[i]=arr1[i]+arr1[i-1];
    }
}

int main()
{
    sieve();

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

    while(t--)
    {
        int a,b;

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

        printf("%d\n",arr1[b]-arr1[a-1]);
    }

    return 0;

}

UVA 10633 - Rare Easy Problem Solution

problem link-click here

think deeply you will get an equation like this N-N/10=(N-M). here (N-M) is given for you so the equation for getting N is N=((N-M)*10)/9. now you will get value of N. From N substitute 1 to check if N-1 also satisfy conditions. I mean if (N-1)-(N-1)/10==(N-M) then output both of them otherwise output only N.

an accepted code is given below:

#include<stdio.h>

int main()
{
    unsigned long long int n;

    while(scanf("%llu",&n)==1 && n!=0)
    {
        unsigned long long int s,q,t;

        s=(n*10)/9;
        q=s-1;

        t=q-(q/10);

        if(t==n)
        {
            printf("%llu %llu\n",q,s);
        }
        else
        {
            printf("%llu\n",s);
        }

    }

    return 0;
}

UVA 11824 - A Minimum Land Price solution

problem link-click here

it's an easy problem. read the statement carefully then i think you must get a way to solve it.

accepted code is given below:

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

 long long int power(int n,int l)
{
    long long int sum=1;

    for(int i=1;i<=l;i++)
    {
        sum=sum*n;
    }

    return sum;
}

int main()
{
    int t;

    cin>>t;

    while(t--)
    {
        int a;
        vector<int> v;

        while(cin>>a && a!=0)
        {
            v.push_back(a);
        }

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

        int l=1;
        long long int sum=0;

        for(int i=v.size()-1;i>=0;i--)
        {
            sum=sum+(2*power(v[i],l));
            l++;
        }

        if(sum>=5000000)
        {
            cout<<"Too expensive"<<endl;
        }
        else
        {
            cout<<sum<<endl;
        }
    }

    return 0;
}

UVA 11219 - How old are you? solution

problem link-click here

accepted code:

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

int main()
{
    int m,d,y,m1,d1,y1,t,i,s;

    while(scanf("%d",&t)==1)
    {

        i=1;

    while(t>=i)
    {

        scanf("%d/%d/%d",&d,&m,&y);
        scanf("%d/%d/%d",&d1,&m1,&y1);

        s=y-y1;

        if(m1>m)
        {
            s--;
        }
        else if(m==m1)
        {
            if(d1>d)
            {
                s--;
            }
        }

        if(s<0)
        {
            printf("Case #%d: Invalid birth date\n",i);
        }
        else if(s>130)
        {
            printf("Case #%d: Check birth date\n",i);
        }
        else
        {
            printf("Case #%d: %d\n",i,s);
        }

        i++;
    }

    }

    return 0;
}

Uva 10370 Above Average solution

problem link-click here

accepted code:

#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
    int n;
    double c,i=0;

    cin>>c;

    while(i<c)
    {
        cin>>n;

        int marks[n+10];
        double avg,j=0,sum=0,ans;

        for(int k=0;k<n;k++)
        {
            cin>>marks[k];
            sum=sum+marks[k];

        }

        avg=sum/n;

        for(int l=0;l<n;l++)
        {
            if(marks[l]>avg)
            {
                j++;
            }
        }

        ans=(j*100)/n;

        cout<<fixed<<setprecision(3)<<ans<<"%"<<endl;

        i++;
    }

    return 0;
}