UVA 10107 - What is the Median?

Problem : What is the Median?
Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers. 
Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}. 
If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4! 

Input 
The input file consists of series of integers X ( 0 <= X < 2^31 ) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces. 

Output 
For each input print the current value of the median. 

Sample Input 
1
3
4
60
70
50
2

Sample Output 
1
2
3
3
4
27

4

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long c,i,ar[10009],x,md;
    c=0;
    while(cin>>ar[c])
    {
 //cout<<"c="<<c<<endl;
        c++;

        sort(ar,ar+c);
        if(c%2==1)
        {
            x=(c+1)/2;
            md=ar[x-1];
            //cout<<x-1<<" "<<md<<endl;
        }
        else
        {
            x=c/2;

            md=ar[x-1]+ar[x];
            md/=2;
            //cout<<x-1<<" "<<ar[x-1]<<" "<<ar[x]<<endl;
        }
        cout<<md<<endl;
    }
    return 0;
}

UVA 146 - ID Codes

Problem : ID Codes
It is 2084 and the year of Big Brother has finally arrived, albeit a century late. In order to exercise greater control over its citizens and thereby to counter a chronic breakdown in law and order, the Government decides on a radical measure--all citizens are to have a tiny microcomputer surgically implanted in their left wrists. This computer will contains all sorts of personal information as well as a transmitter which will allow people's movements to be logged and monitored by a central computer. (A desirable side effect of this process is that it will shorten the dole queue for plastic surgeons.) 
An essential component of each computer will be a unique identification code, consisting of up to 50 characters drawn from the 26 lower case letters. The set of characters for any given code is chosen somewhat haphazardly. The complicated way in which the code is imprinted into the chip makes it much easier for the manufacturer to produce codes which are rearrangements of other codes than to produce new codes with a different selection of letters. Thus, once a set of letters has been chosen all possible codes derivable from it are used before changing the set. 
For example, suppose it is decided that a code will contain exactly 3 occurrences of `a', 2 of `b' and 1 of `c', then three of the allowable 60 codes under these conditions are: 
      abaabc
      abaacb
      ababac
These three codes are listed from top to bottom in alphabetic order. Among all codes generated with this set of characters, these codes appear consecutively in this order. 
Write a program to assist in the issuing of these identification codes. Your program will accept a sequence of no more than 50 lower case letters (which may contain repeated characters) and print the successor code if one exists or the message `No Successor' if the given code is the last in the sequence for that set of characters. 

Input and Output
Input will consist of a series of lines each containing a string representing a code. The entire file will be terminated by a line consisting of a single #. 
Output will consist of one line for each code read containing the successor code or the words `No Successor'. 

Sample input
abaacb
cbbaa
#

Sample output
ababac

No Successor

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char ar[100000];
    while(cin>>ar)
    {
        long long l=strlen(ar);
        if(ar[0]=='#'&&l==1)
        break;

        if(next_permutation(ar,ar+l))
            cout<<ar<<endl;
        else
            cout<<"No Successor"<<endl;
    }
    return 0;
}

UVA 10038 - Jolly Jumpers

Problem E: Jolly Jumpers
A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance, 
1 4 2 3
is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper. 

Input
Each line of input contains an integer n <= 3000 followed by n integers representing the sequence. 

Output
For each line of input, generate a line of output saying "Jolly" or "Not jolly". 

Sample Input
4 1 4 2 3
5 1 4 2 -1 6

Sample Output
Jolly

Not jolly


My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m,i,x,s,f,mx,ar[3009];
    while(cin>>n)
    {
        x=0;
        f=0;
        mx=-1;
        for(i=0; i<n; i++)
        {
            cin>>m;
            s=abs(m-x);
            if(i>0)
            {
                ar[i-1]=s;
                //cout<<s<<endl;
            }
            x=m;
        }
        sort(ar,ar+n-1);
        for(i=1; i<n-1; i++)
            {
                if(ar[i]-ar[i-1]!=1||ar[0]!=1)
                {
                    f=1;
                    break;
                }
            }
        if(f==0)
            cout<<"Jolly"<<endl;
        else
            cout<<"Not jolly"<<endl;
    }
    return 0;
}

UVA 490 - Rotating Sentences

Problem : Rotating Sentences
In ``Rotating Sentences,'' you are asked to rotate a series of input sentences 90 degrees clockwise. So instead of displaying the input sentences from left to right and top to bottom, your program will display them from top to bottom and right to left. 

Input and Output
As input to your program, you will be given a maximum of 100 sentences, each not exceeding 100 characters long. Legal characters include: newline, space, any punctuation characters, digits, and lower case or upper case English letters. (NOTE: Tabs are not legal characters.) 
The output of the program should have the last sentence printed out vertically in the leftmost column; the first sentence of the input would subsequently end up at the rightmost column. 

Sample Input
Rene Decartes once said,
"I think, therefore I am."

Sample Output
"R
Ie
 n
te
h 
iD
ne
kc
,a
 r
tt
he
es
r
eo
fn
oc
re
e
 s
Ia
 i
ad
m,
.
"

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1009][109];
    long long i,l,c,ll,mx,j;
    //while(true)

    c=0;
    mx=-1;
    while(gets(s[c]))
    {
        ll=strlen(s[c]);
        if(mx<ll)
            mx=ll;
        c++;

    }
    //cout<<"mx="<<mx<<endl;
    for(i=0; i<mx; i++)
    {

        for(j=c-1; j>=0; j--)
        {
            l=strlen(s[j]);
            if(i<l)
                cout<<s[j][i];
            else
                cout<<" ";
        }
        cout<<endl;
    }

    return 0;
}

UVA 10008 - What's Cryptanalysis?

Problem : What’s Cryptanalysis?
Cryptanalysis is the process of breaking someone else's cryptographic writing. This sometimes involves some kind of statistical analysis of a passage of (encrypted) text. Your task is to write a program which performs a simple analysis of a given text. 

Input  
The first line of input contains a single positive decimal integer n. This is the number of lines which follow in the input. The next n lines will contain zero or more characters (possibly including whitespace). This is the text which must be analyzed. 

Output  
Each line of output contains a single uppercase letter, followed by a single space, then followed by a positive decimal integer. The integer indicates how many times the corresponding letter appears in the input text. Upper and lower case letters in the input are to be considered the same. No other characters must be counted. The output must be sorted in descending count order; that is, the most frequent letter is on the first output line, and the last line of output indicates the least frequent letter. If two letters have the same frequency, then the letter which comes first in the alphabet must appear first in the output. If a letter does not appear in the text, then that letter must not appear in the output. 

Sample Input  

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!!  Is this question easy?

Sample Output  

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1



My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,l,j,mx;
    char s[1000000],aa;
    while(cin>>n)
    {
        map<char,long long>mp;
        getchar();
        for(i=1; i<=n; i++)
        {

            gets(s);
            l=strlen(s);
            for(j=0; j<l; j++)
            {
                if((s[j]>='a'&&s[j]<='z')||(s[j]>='A'&&s[j]<='Z'))
                {
                    if(s[j]>='a'&&s[j]<='z')
                        mp[s[j]-32]++;
                    else mp[s[j]]++;
                }
            }
            //cout<<s<<endl;
        }
        for(char c='A'; c<='Z'; c++)
        {
            mx=-1;
            for(char cc='A'; cc<='Z'; cc++)
            {
                if(mx<mp[cc])
                {
                    mx=mp[cc];
                    aa=cc;
                }
            }
            if(mx>0)
            cout<<aa<<" "<<mx<<endl;
            mp[aa]=0;
        }
    }
        return 0;
}

UVA 264 - Count on Cantor

Problem : Count on Cantor
One of the famous proofs of modern mathematics is Georg Cantor’s demonstration that the set of
rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers
as shown in the diagram below.
1/1 1/2 1/3 1/4 1/5 : : :
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
In the above diagram, the first term is 1/1, the second term is 1/2, the third term is 2/1, the fourth
term is 3/1, the fifth term is 2/2, and so on.

Input and Output
You are to write a program that will read a list of numbers in the range from 1 to 107 and will print
for each number the corresponding term in Cantor’s enumeration as given below. No blank line should
appear after the last number.
The input list contains a single number per line and will be terminated by end-of-file.

Sample input
3
14
7

Sample output
TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS ¼

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,j,x,y,c;
    while(cin>>n)
    {
        i=1;
        j=1;
        c=1;
        while(c<n)
        {
            c++;
            if(i==1&&j%2==1)
                j++;
            else if(i==1&&j%2==0)
            {
                i++;
                j--;
            }
             else if(j==1&&i%2==1)
            {
                i--;
                j++;
            }
            else if(j==1&&i%2==0)
            {
                i++;

            }
            else if((i+j)%2==0)
            {
                i--;
                j++;
            }
            else if((i+j)%2==1)
            {
                i++;
                j--;
            }
            //cout<<c<<" "<<i<<" "<<j<<endl;
        }
        cout<<"TERM "<<c<<" IS "<<i<<"/"<<j<<endl;
    }
    return 0;
}

UVA 499 - What's The Frequency, Kenneth?

Problem : What's The Frequency, Kenneth?
#include <stdio.h>

main()
{
  int i;
  char *suffix[]= { "st", "nd", "rd" };
  char *item[]= { "Unix" , "cat", "sed", "awk", "grep", "ed", "vi"};

  printf("In the beginning, there was nothing.\n");
  for (i= 0; i < 7; i++)
    printf("And on the %d%s day, God created %s. And it was good.\n",
           i + 1, (i < 3) ? suffix[i] : "th", item[i]);
}
But then God saw that vi led people into temptation. Instead of choosing the righteous ways of make, dbx, and RCS, people used long command lines, printf(), and tape backups. 
So God decreed, ``I see that Engineers have thus defiled my vi. And so, I shall create emacs, an editor more powerful than words. Further, for each instantiation vi hitherto, the Engineer responsible shalt perform Penance. And lo, the Penance wilt be painful; there will be much wailing and gnushingof teeth. The Engineer will read many lines of text. For each line of text, the Engineer must tell me which letters occur the most frequently.'' 
``I charge you all with My Golden Rule: 'Friends shalt not let friends use vi'.'' 

Input and Output
Each line of output should contain a list of letters that all occured with the highest frequency in the corresponding input line, followed by the frequency. 
The list of letters should be an alphabetical list of upper case letters followed by an alphabetical list of lower case letters. 

Sample Input
When riding your bicycle backwards down a one-way street, if the
wheel falls of a canoe, how many ball bearings does it take to fill
up a water buffalo?
Hello Howard.

Sample Output
e 6
al 7
a 3
Hlo 2

My accepted code is given below:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    char s[1000000];

    long long i,l,mx;

    char ii;

    while(gets(s))

    {

        //cout<<s<<endl;

        map<char,int> mp;

        l=strlen(s);

        mx=-1;

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

        {

            if((s[i]>='a'&s[i]<='z')||(s[i]>='A'&s[i]<='Z'))

            {

                mp[s[i]]++;

                if(mp[s[i]]>mx)

                    mx=mp[s[i]];

            }

        }

        //cout<<mx<<endl;

        for(ii='A'; ii<='Z'; ii++)

        {

            if(mp[ii]==mx)

                cout<<ii;

        }

        for(ii='a'; ii<='z'; ii++)

        {

            if(mp[ii]==mx)

                cout<<ii;

        }

        cout<<" "<<mx<<endl;

    }

    return 0;

}

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
*/