UVA 10019 - Funny Encryption Method

Problem : Funny Encryption Method

History : 
A student from ITESM Campus Monterrey plays with a new encryption method for numbers. These method consist of the following steps: 
Steps :  Example 
1) Read the number N to encrypt M = 265 
2) Interpret N as a decimal number X1= 265 (decimal) 
3) Convert the decimal interpretation of N to its binary representation X1= 100001001 (binary) 
4) Let b1 be equal to the number of 1’s in this binary representation B1= 3 
5) Interpret N as a Hexadecimal number X2 = 265 (hexadecimal) 
6) Convert the hexadecimal interpretation of N to its binary representation X2 = 1001100101 
7) Let b2 be equal to the number of 1’s in the last binary representation B2 = 5 
8) The encryption is the result of  M xor (b1*b2) M xor (3*5) = 262 
This student failed Computational Organization, that’s why this student asked the judges of ITESM Campus Monterrey internal ACM programming Contest to ask for the numbers of 1’s bits of this two representations so that he can continue playing. 

Task : 
You have to write a program that read a Number and give as output the number b1 and b2 

The Input
The first line will contain a number N which is the number of cases that you have to process. Each of the following N Lines ( 0<N<=1000) will contain the number M (0<M<=9999, in decimal representation)  which is the number the student wants to encrypt. 

The Output
You will have to output N lines, each containing the number b1 and b2 in that order, separated by one space  corresponding to that lines number to crypt 

Sample Input
3
265
111
1234 

Sample Output
3 5 
6 3 

5 5

My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
long long con(long long m)
{
    long long a=0;
    //cout<<"m="<<m<<endl;
    while(m)
        {

            a+=m%2;
            //cout<<"x="<<a<<endl;
            m/=2;
        }
        //cout<<"a="<<a<<endl;
        return a;
}
int main()
{
    long long n,m,a,b,t,l,i,sum,c;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>s;
        l=s.length();
        sum=0;
        c=1;

        for(i=l-1;i>=0;i--)
        {
           sum+=(s[i]-'0')*c;
           c*=10;
           //cout<<sum<<endl;
        }

        a=con(sum);
        //cout<<"a"<<a<<endl;
        sum=0;
        c=1;
        for(i=l-1;i>=0;i--)
        {
           sum+=(s[i]-'0')*c;
           c*=16;
           //cout<<sum<<endl;
        }
        b=con(sum);
        //cout<<"sum="<<sum<<endl;
        cout<<a<<" "<<b<<endl;
    }
    return 0;
}

UVA 494 - Kindergarten Counting Game

Problem : Kindergarten Counting Game
Everybody sit down in a circle. Ok. Listen to me carefully. 
``Woooooo, you scwewy wabbit!'' 
Now, could someone tell me how many words I just said? 

Input and Output
Input to your program will consist of a series of lines, each line containing multiple words (at least one). A ``word'' is defined as a consecutive sequence of letters (upper and/or lower case). 
Your program should output a word count for each line of input. Each word count should be printed on a separate line. 

Sample Input
Meep Meep!
I tot I taw a putty tat.
I did! I did! I did taw a putty tat.
Shsssssssssh ... I am hunting wabbits. Heh Heh Heh Heh ...

Sample Output
2
7
10
9



My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1000000];
    long l,c,i;
    while(gets(s))
    {
        l=strlen(s);
        c=0;
        for(i=0;i<l;i++)
        {
            if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
                {
                    while((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
                    {
                        if(i>l-1)
                            break;
                        i++;


                    }
                     c++;
                }
        }
        cout<<c<<endl;
    }
    return 0;
}

UVA 483 - Word Scramble

Problem: Word Scramble
Write a program that will reverse the letters in each of a sequence of words while preserving the order of the words themselves. 

Input
The input file will consist of several lines of several words. Words are contiguous stretches of printable characters delimited by white space. 

Output
The output will consist of the same lines and words as the input file. However, the letters within each word must be reversed. 

Sample Input
I love you.
You love me.
We're a happy family.

Sample Output
I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf

My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1000000];
    long long l,i,c,c2,j;
    while(gets(s))
    {
        l=strlen(s);
        c2=0;
        for(i=0; i<l; i++)
        {
            //cout<<"x";
            if(s[i]==' '||i==l-1)
            {
                //cout<<"x="<<s[i-1];
                if(i==l-1)
                    c=i;
                else
                    c=i-1;

                for(j=c; j>=c2; j--)
                {
                    cout<<s[j];
                    //int x=1;
                }
                if(i!=l-1)
                    cout<<s[i];
                c2=i+1;
            }
        }
         cout<<endl;
    }
    return 0;
}

uva 458 - The Decoder

Problem:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=399

The Decoder:

Write a complete program that will correctly decode a set of characters into a valid message. Your program should read a given file of a simple coded set of characters and print the exact message that the characters contain. The code key for this simple coding is a one for one character substitution based upon a single arithmetic manipulation of the printable portion of the ASCII character set.
Input and Output
For example: with the input file that contains:
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
your program should print the message:
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.
Your program should accept all sets of characters that use the same encoding scheme and should print the actual message of each set of characters.
Sample Input
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
Sample Output
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.


My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    char c;
    long long l,i;
    while(cin>>s)
    {
        l=s.length();
        for(i=0;i<l;i++)
        {
            c=s[i]-7;
            cout<<c;
        }
        cout<<endl;
    }
    return 0;
}

UVA 10653 - Bombs! NO they are Mines!!

Problem Link:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1594

Bombs! NO they are Mines!!
Input: standard input
Output: standard output
Time Limit: 4 seconds

It's the year 3002. The robots of "ROBOTS 'R US (R:US)" have taken control over the world. You are one of the few people who remain alive only to act as their guinea pigs. From time to time the robots use you to find if they have been able to become more intelligent. You, being the smart guy, have always been successful in proving to be more intelligent.
Today is your big day. If you can beat the fastest robot in the IRQ2003 land, you'd be free. These robots are intelligent. However, they have not been able to overcome a major deficiency in their physical design -- they can only move in 4 directions: Forward, Backward, Upward and Downward. And they take 1 unit time to travel 1 unit distance. As you have got only one chance, you're planning it thoroughly. The robots have left one of the fastest robot to guard you. You'd need to program another robot which would carry you through the rugged terrain. A crucial part of your plan requires you to find the how much time the guard robot would need to reach your destination. If you can beat him, you're through.
 
We must warn you that the IRQ2003 land is not a pleasant place to roam. The R:US have dropped numerous bombs while they invaded the human land. Most of the bombs have exploded. Still some of the bombs remain acting as land mines. We have managed to get a map that shows the unsafe regions of the IRQ2003 land; unfortunately your guard has a copy of the map, too. We know that at most 40% of the area can be unsafe. If you are to beat your guard, you'd have to find his fastest route long before he finds it.
Input
Input consists of several test cases. Each test begins with two integers R (1 <= R <= 1000), C (1 <= C <= 1000) -- they give you the total number of rows and columns in the grid map of the land. Then follows the grid locations of the bombs. It starts with the number of rows, (0 <= rows <= R) containing bombs. For each of the rows, you'd have one line of input. These lines start with the row number, followed by the number of bombs in that row. Then you'd have the column locations of that many bombs in that row. The test case ends with the starting location (row, column) followed by your destination (row, column). All the points in the region is in the range (0,0) to (R-1, C-1). Input ends with a test case where R=0 and C=0, you must not process this test case.
Output
For each test case, print the time the guard robot would take to go from the starting location to the destination.
Sample Input                           Output for Sample Input
10 10
9
0 1 2
1 1 2
2 2 2 9
3 2 1 7
5 3 3 6 9
6 4 0 1 2 7
7 3 0 3 8
8 2 7 9
9 3 2 3 4
0 0
9 9
0 0 18

My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
long long n,m,sx,sy,ex,ey;
long long ar[1009][1009],visit[1009][1009],cost[1009][1009];
long long br[]= {1,-1,0,0};
long long cr[]= {0,0,1,-1};
int bsf(int x,int y)
{
    queue<long long>q;
    memset(visit,0,sizeof visit);
    memset(cost,0,sizeof cost);
    long long fx,fy,i,j,vx,vy,f;
    q.push(x);
    q.push(y);
    visit[x][y]=1;
    cost[x][y]=0;
    //cout<<"f"<<endl;
    while(!q.empty())
    {
        fx=q.front();
        q.pop();
        fy=q.front();
        q.pop();
        f=0;
        //cout<<fx<<" "<<fy<<endl;
        for(i=0; i<4; i++)
        {
            vx=fx+br[i];
            vy=fy+cr[i];
            if(vx>=0&&vx<n&&vy>=0&&vy<m&&ar[vx][vy]!=1)
            {
                if(visit[vx][vy]==0)
                {
                    q.push(vx);
                    q.push(vy);
                    visit[vx][vy]=1;
                    cost[vx][vy]=cost[fx][fy]+1;
                    //cout<<vx<<" "<<vy<<" "<<cost[vx][vy]<<endl;
                }
            }
            if(vx==ex&&vy==ey)
            {
                cout<<cost[vx][vy]<<endl;
                f=1;
                break;
            }
        }
        if(f==1)
            break;
    }
}
int main()
{
    long long i,j,t,a,b,x;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
            //cout<<"test"<<endl;
        cin>>t;
        memset(ar,0,sizeof ar);
        for(i=0; i<t; i++)
        {
           // cout<<"t="<<i<<endl;
            cin>>a>>x;
            for(j=0; j<x; j++)
            {
                cin>>b;
                ar[a][b]=1;
            }

        }
        cin>>sx>>sy>>ex>>ey;
        bsf(sx,sy);
    }
    return 0;
}
/*
1 0 1
0 1 1
2 0 2
1 1 2
3 0 3
2 1 3
4 0 4
5 0 5
4 1 5
5 1 6
4 2 6
5 2 7
3 2 7
4 3 7
3 3 8
4 4 8
2 3 9
3 4 9
5 4 9
4 5 9
1 3 10
2 4 10
3 5 10
6 4 10
5 5 10
4 6 10
0 3 11
1 4 11
2 5 11
3 6 11
7 4 11
6 5 11
6 3 11
4 7 11
0 4 12
1 5 12
2 6 12
8 4 12
7 5 12
6 6 12
5 7 12
4 8 12
0 5 13
1 6 13
2 7 13
8 5 13
8 3 13
7 6 13
5 8 13
3 8 13
4 9 13
0 6 14
1 7 14
2 8 14
9 5 14
8 6 14
8 2 14
7 7 14
6 8 14
3 9 14
0 7 15
1 8 15
9 6 15
7 2 15
8 1 15
6 9 15
0 8 16
1 9 16
9 7 16
7 1 16
9 1 16
8 0 16
7 9 16
0 9 17
9 8 17
9 0 17
8 8 18
9 9 18
ans=17
*/

UVA 136 - Ugly Numbers

Problem : Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 
shows the first 11 ugly numbers. By convention, 1 is included. 
Write a program to find and print the 1500'th ugly number. 

Input and Output
There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed. 

Sample output
The 1500'th ugly number is <number>. 

My accepted code is given below:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,n,i,ar[1599]={0},x,y,z;
    a=b=c=n=1;
    ar[1]=1;
    while(n!=1501)
    {
        //cout<<ar[n]<<endl;
        x=2*ar[a];
        y=3*ar[b];
        z=5*ar[c];
        ar[++n]=min(x,min(y,z));
        if(ar[n]==x)
            a++;
        if(ar[n]==y)
            b++;
            if(ar[n]==z)
            c++;
    }
    cout<<"The 1500'th ugly number is "<<ar[1500]<<"."<<endl;
}

UVA 567 - Risk

Problem:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=508

Risk :

Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country.

During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one.

The following connection diagram illustrates the first sample input.

Input
Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many ``higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (  ) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (  ) indicating the starting and ending countries for a possible conquest.

There can be multiple test sets in the input file; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration.

Output
For each input set, your program should print the following message ``Test Set #T" where T is the number of the test set starting with 1 (left-justified starting in column 11).
The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A right-justified in columns 1 and 2; the string `` to " in columns 3 to 6; the destination country code B right-justified in columns 7 and 8; the string ``: " in columns 9 and 10; and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set left-justified starting in column 11. Following all result lines of each input set, your program should print a single blank line.

Sample Input
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16

Sample Output
Test Set #1
 1 to 20: 7
 2 to  9: 5
19 to  5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
 1 to 20: 4
 8 to 20: 5
15 to 16: 2
11 to  4: 1
 7 to 13: 3
 2 to 16: 4

My accepted code is given below:

Code:
#include<bits/stdc++.h>
using namespace std;
long long bsf(long long start,long long end,map<long long,vector<long long> >vec)
{
    map<long long,long long>visit,lebel;
    long long frnt,l,i,v;
    visit[start]=1;
    queue<long long>q;
    q.push(start);
    lebel[start]=0;
    while(!q.empty())
    {
        frnt=q.front();
        //cout<<frnt<<"->";
        q.pop();
        l=vec[frnt].size();
        for(i=0; i<l; i++)
        {
            v=vec[frnt][i];
            if(visit[v]==0)
            {
                visit[v]=1;
                q.push(v);
                lebel[v]=lebel[frnt]+1;
            }
        }
    }
    return lebel[end];
}
int main()
{
    long long n,i,a,m,x,j,y,c=1,k,nn;
    while(cin>>n)
    {
        map<long long,vector<long long> >vec;
       // cout<<"AAA"<<endl;
        for(i=0; i<n; i++)
        {
            cin>>a;
            vec[1].push_back(a);
            vec[a].push_back(1);
            //cout<<"kj";
        }
        for(i=2; i<=19; i++)
        {
            cin>>nn;
            for(j=0; j<nn; j++)
            {
                cin>>a;
                vec[i].push_back(a);
                vec[a].push_back(i);
            }
        }
        cout<<"Test Set #"<<c++<<endl;
        cin>>m;

        for(k=0; k<m; k++)
        {
            cin>>x>>y;
            //cout<<"dsjn"<<endl;
            printf("%2lld",x);
            cout<<" to ";
            printf("%2lld",y);
            cout<<": "<<bsf(x,y,vec)<<endl;
        }
        cout<<endl;
    }
}
/*
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16
*/