A. Local Extrema / Educational Codeforces Round 32

A. Local Extrema


time limit per test
1 second


memory limit per test
256 megabytes


input
standard input


output
standard output



You are given an array a. Some element of this array ai is a local minimum iff it is strictly less than both of its neighbours (that is, ai < ai - 1and ai < ai + 1). Also the element can be called local maximum iff it is strictly greater than its neighbours (that is, ai > ai - 1 and ai > ai + 1). Since a1 and an have only one neighbour each, they are neither local minima nor local maxima.

An element is called a local extremum iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array.



Input

The first line contains one integer n (1 ≤ n ≤ 1000) — the number of elements in array a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000) — the elements of array a.



Output

Print the number of local extrema in the given array.



Examples



input
3
1 2 3



output
0



input
4
1 5 2 5



output
2

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    long long n,a,b,i,c;
    long long ar[1000];
    while(cin>>n)
    {
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
        }
        c=0;

        for(i=0; i<n; i++)
        {
            //cout<<ar[i]<<endl;
            if(i>0&&i<n-1)
            {
                if((ar[i]>ar[i-1]&&ar[i]>ar[i+1])||((ar[i]<ar[i-1]&&ar[i]<ar[i+1])))
                {
                    c++;
                    //cout<<ar[i]<<" "<<ar[i+1]<<" "<<ar[i-1]<<" "<<i<<endl;
                }
            }
        }
        cout<<c<<endl;
    }
    return 0;
}

UVA 439 - Knight Moves

Problem:

Problem:

A friend of you is doing research on the Traveling Knight Problem (TKP)where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy. Of course you know that it is vice versa. So you offer him to write a program that  solves the ”difficult” part. Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b

.

Input

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a..h) representing the column and a digit (1..8) representing the row on the chessboard.

Output

For each test case, print one line saying ‘ To get from xx to yy takes n knight moves.’.

Sample Input

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.

Code:
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int ,int>
int ar[]= {1, -1, 1, -1, 2, 2, -2, -2};
int br[]= {2, 2, -2, -2, 1, -1, 1, -1};
int vis[20][20];
int cost[20][20];
char c1[10],c2[10];
int bsf(int a1,int b1,int a2,int b2)
{
    queue<pii>q;
    memset(vis,0,sizeof vis);
    // memset(cost,0,sizeof vis);
    q.push(pii(a1,b1));
    vis[a1][b1]=1;
    cost[a1][b1]=0;
    while(!q.empty())
    {
        pii top=q.front();
        q.pop();
        if(top.first==a2&&top.second==b2)
        {
            cout<<"To get from "<<c1<<" to "<<c2<<" takes "<<cost[a2][b2]<<" knight moves."<<endl;
            return 0;
        }
        for(int i=0; i<8; i++)
        {
            int x=top.first+ar[i];
            int y=top.second+br[i];
            if(x>0&&x<=8&&y>0&&y<=8&&vis[x][y]==0)
            {
                q.push(pii(x,y));
                vis[x][y]=1;
                cost[x][y]=cost[top.first][top.second]+1;
            }
        }
    }
}
int main()
{
    int i,j,a1,a2,b1,b2;

    while(cin>>c1>>c2)
    {
        a1=c1[0]-96;
        b1=c1[1]-'0';
        a2=c2[0]-96;
        b2=c2[1]-'0';
        bsf(a1,b1,a2,b2);
        //cout<<a1<<" "<<b1<<" "<<a2<<" "<<b2<<endl;
    }
    return 0;
}

UVA 10305 - Ordering Tasks

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1<=n<=100 and

m.n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be

m lines with two integers i and j , representing the fact that task i must be executed before task j . An instance with n = m= 0 will nish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.
Sample Input

5 4

1 2

2 3

1 3

1 5

0 0

Sample Output

1 4 2 5 3

MY accepted code Code:

#include<bits/stdc++.h>

using namespace std;

long long visited[100];

vector <int> grp[200];

map<int,int>vis;

stack<int>st;

int n;

int topologicalSortUtill(int v)

{

    vis[v] = 1;

    int l=grp[v].size();

    int u;

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

    {

        u=grp[v][i];

        if (!vis[u])

            topologicalSortUtill(u);

    }

    st.push(v);

}

int  topologicalSort()

{

    for(int i=1; i<=n; i++)

        vis[i]=0;

    for(int i=1; i<=n; i++)

        if(vis[i]==0)

            topologicalSortUtill(i);

            int c=0;

    while(st.empty()==0)

    {

        c++;

        cout<<st.top();

        if(c<n)

            cout<<" ";

        st.pop();

    }

    cout<<endl;

}

int main()

{

    int m,i,j,a,b;

    while(cin>>n>>m)

    {

        if(n==0&&m==0)

            break;

        for(i=1; i<=m; i++)

        {

            cin>>a>>b;

            grp[a].push_back(b);

        }

        //for(i=0;i<n;i++)

        topologicalSort();

    }

    return 0;

}

/*

6 6

5 2

5 0

4 0

4 1

2 3

3 1

*/

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/B. Keyboard Layouts

Problem:

B. Keyboard Layouts

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order.

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.

Input

The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.

Output

Print the text if the same keys were pressed in the second layout.

Examples

input

qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017

output

HelloVKCup2017

input

mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7

output

7uduGUDUUDUgudu7

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char ar[50],br[50];
    string cr;
    long long i,j;
    while(cin>>ar>>br)
    {
        map<char,char>mp;
        for(i=0; i<strlen(ar); i++)
        {
            mp[ar[i]]=br[i];
            mp[ar[i]-32]=br[i]-32;
        }
        /*for(int c=0;c<=25;c++)
        {
            cout<<mp[ar[c]]<<" "<<mp[ar[c]-32]<<endl;
        }*/
        getchar();
        getline(cin,cr);
       //cout<<"x="<<cr<<endl;
//cout<<"x="<<cr<<endl;
long long ll=cr.length();
//cout<<"l="<<ll<<endl;
        for(i=0; i<ll; i++)
        {
            //cout<<i<<endl;
            if((cr[i]>='a'&&cr[i]<='z')||(cr[i]>='A'&&cr[i]<='Z'))
            cout<<mp[cr[i]];
            else
                cout<<cr[i];
        }
        cout<<endl;
    }
    return 0;
}
//abcdefghijklmnopqrstuvwxyz

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/A. Unimodal Array

Problem:

A. Unimodal Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Array of integers is unimodal, if:

• it is strictly increasing in the beginning;
• after that it is constant;
• after that it is strictly decreasing.

The first block (increasing) and the last block (decreasing) may be absent. It is allowed that both of this blocks are absent.

For example, the following three arrays are unimodal: [5, 7, 11, 11, 2, 1], [4, 4, 2], [7], but the following three are not unimodal: [5, 5, 6, 6, 1], [1, 2, 1, 2], [4, 5, 5, 6].

Write a program that checks if an array is unimodal.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000) — the elements of the array.

Output

Print "YES" if the given array is unimodal. Otherwise, print "NO".

You can output each letter in any case (upper or lower).

Examples

input

6
1 5 5 5 4 2

output

YES

input

5
10 20 30 20 10

output

YES

input

4
1 2 1 2

output

NO

input

7
3 3 3 3 3 3 3

output

YES

Note

In the first example the array is unimodal, because it is strictly increasing in the beginning (from position 1 to position 2, inclusively), that it is constant (from position 2 to position 4, inclusively) and then it is strictly decreasing (from position 4 to position 6, inclusively).

My accepted Code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long ar[1009],i,j,n,x,temp,f,ff,fff;
    while(cin>>n)
    {
        f=0;
        ff=0;
        fff=0;
        for(i=0;i<n;i++)
        {
            cin>>x;
            if(i==0)
                temp=x;
                else
                {
                    if((f==-1&&temp<x)||(fff==-1&&temp<x)||(f==-1&&temp==x))
                        ff=1;
                        //if()
                    else if(temp>x)
                        f=-1;
                         else if(temp==x)
                        fff=-1;
                         // cout<<f<<" "<<ff<<" "<<temp<<" "<<x<<endl;
                        temp=x;
                }

        }
        if(ff==1)
        cout<<"NO"<<endl;
        else
         cout<<"YES"<<endl;

    }
    return 0;
}

UVA 673 - Parentheses Balance

problem:
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your
program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses ‘()’ and ‘[]’, one string
a line.
Output
A sequence of ‘Yes’ or ‘No’ on the output file.
Sample Input
3
([])
(([()])))
([()[]()])()
Sample Output
Yes
No

Yes
My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    long long i,j,n,l,f;
    cin>>n;

    getchar();
    while(n--)
    {

        getline(cin,s);
        //cout<<"x="<<s<<endl;
 l=s.length();
        stack<char>q;
        if(l%2!=0)
            cout<<"No"<<endl;

        else
        {
            f=0;

            for(i=0; i<l; i++)
            {
                if(s[i]=='('||s[i]=='[')
                {
                    //cout<<"1";
                    q.push(s[i]);
                }
               else if(!q.empty()&&s[i]==')'&&q.top()=='(')
                {
                   // cout<<"2";
                    q.pop();
                }
                    else if(!q.empty()&&s[i]==']'&&q.top()=='[')
                {
                    //cout<<"3";
                    q.pop();
                }
                else
                {
                    q.push(s[i]);
                }
            }

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

    return 0;
}

UVA 572 - Oil Deposits

Solution of the  UVA 572 - Oil Deposits:
problem:
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits.
GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides
the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to
determine whether or not the plot contains oil.
A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the
same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to
determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number
of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input;
otherwise 1 m 100 and 1 n 100. Following this are m lines of n characters each (not counting
the end-of-line characters). Each character corresponds to one plot, and is either ‘*’, representing the
absence of oil, or ‘@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same
oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain
more than 100 pockets.
Sample Input
1 1
*3
5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output

0
1
2
2
My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
//map <int,vector <int > >graph;
char ar[109][109];
long long n,m;
#define pii pair<long long,long long>
long long a[]= {0,0,1,-1,1,-1,-1,1};
long long b[]= {1,-1,0,0,1,1,-1,-1};
int bsf(long long ii,long long jj)
{
    long long i,j,x,y;
    queue<pii> q;
    q.push(pii(ii,jj));
    while(!q.empty())
    {
        pii top=q.front();
        q.pop();
        for(i=0; i<8; i++)
        {


            x=top.first+a[i];
            y=top.second+b[i];
            if(x>=0&&x<n&&y>=0&&y<m&&ar[x][y]=='@')
            {

                    q.push(pii(x,y));
                    ar[x][y]='*';

            }

        }
    }
}
int main()
{
    long long i,j;
    while(cin>>n>>m)
    {
        if(n==0)
            break;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                cin>>ar[i][j];
                //visit[i][j]=0;

            }
        }
        long long count=0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(ar[i][j]=='@')
                {
                    bsf(i,j);
                    count++;
                }

            }
        }
        cout<<count<<endl;
        //cout<<"kjh"<<endl;
    }
    return 0;
}

Codeforces Round #422 (Div. 2) A. I'm bored with life

Problem:

A. I'm bored with life

 

 

Holidays have finished. Thanks to the help of the hacker Leha, Noora managed to enter the university of her dreams which is located in a town Pavlopolis. It's well known that universities provide students with dormitory for the period of university studies. Consequently Noora had to leave Vičkopolis and move to Pavlopolis. Thus Leha was left completely alone in a quiet town Vičkopolis. He almost even fell into a depression from boredom!

Leha came up with a task for himself to relax a little. He chooses two integers A and B and then calculates the greatest common divisor of integers "A factorial" and "B factorial". Formally the hacker wants to find out GCD(A!, B!). It's well known that the factorial of an integer x is a product of all positive integers less than or equal to x. Thus x! = 1·2·3·...·(x - 1)·x. For example 4! = 1·2·3·4 = 24. Recall that GCD(x, y) is the largest positive integer q that divides (without a remainder) both x and y.

Leha has learned how to solve this task very effective. You are able to cope with it not worse, aren't you?

Input

The first and single line contains two integers A and B (1 ≤ A, B ≤ 109, min(A, B) ≤ 12).

Output

Print a single integer denoting the greatest common divisor of integers A! and B!.

Example

input

4 3

output

6

Note

Consider the sample.

4! = 1·2·3·4 = 24. 3! = 1·2·3 = 6. The greatest common divisor of integers 24 and 6 is exactly 6.

My accepted code is given below:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long a,b,i,mn,sum;

    while(cin>>a>>b)

    {

        mn=min(a,b);

        sum=1;

        while(mn)

        {

            sum*=mn;

            mn--;

        }

        cout<<sum<<endl;

    }

    return 0;

}